2021牛客寒假算法基础集训营2 F.牛牛与交换排序(双端队列翻转)
内容导读
互联网集市收集整理的这篇技术教程文章主要介绍了2021牛客寒假算法基础集训营2 F.牛牛与交换排序(双端队列翻转)，小编现在分享给大家，供广大互联网技能从业者学习和参考。文章包含3106字，纯文字阅读大概需要5分钟。
内容图文
F.牛牛与交换排序
题目链接：https://ac.nowcoder.com/acm/contest/9982/F
题目描述：
牛牛有一个数组，数组元素是1到n的排列，即数组的值在1~n范围内，且每个数字仅出现1次。
牛牛想要将该数组变为升序排列的，他可以进行如下的操作。
首先他要确定一个长度k，k的范围在1~n之间。
接下来他将会进行若干次操作。在每轮操作中他都可以选择一段长度为k的子数组，然后进行区间的翻转操作。
他可以做任意次数的操作，但是要求他每次选择的子数组区间满足li ≤ li+1，并且区间长度等于一开始选定的k，也就是说一旦某一次操作选择了数组的某个位置进行区间翻转操作，下一次做区间翻转的位置将会比上一次更靠右。
牛牛发现，并不总是存在一个k可以使得数组排序变为有序，请你告诉牛牛是否存在一个k能够在满足规则的情况下完成排序。
输入描述：
第一行输入一个正整数n(1≤n≤10^5)表示数组的大小。
接下来输出一行n个正整数表示一个排列，即每个数的大小范围在1到n且每个正整数仅出现一次。
输出描述：
如果存在至少一个k能够使牛牛完成排序，请先在一行中输出一个"yes"，然后另起一行输出一个可以满足排序的k，要求k的范围在[1,n]之间，如果有多解，你可以输出任意一个。
反之如果不存在任何一个k可以完成排序，请直接在一行输出一个"no"。
示例1：
输入
5
5 2 1 4 3
输出
yes
3
说明
首先翻转[1,3]区间，然后翻转[3,5]区间
示例2：
输入
5
1 2 3 4 5
输出
yes
1
说明
由于本来就有序，其实不需要做任何操作，所以随便输出一个k即可。
示例3：
输入
5
5 4 3 2 1
输出
yes
5
说明
直接翻转[1,5]区间
备注：
如果有多解，你可以输出任意范围在[1,n]之间的k。
解题思路：
由于每一次翻转的区间必须在上一次的右边，因此第一次如果不把1翻到位，则1就回不去了，因此可得k的值即为：1的位置与1的差值（若1到位则是2的位置与2的差值……i的位置与i的差值）。
接下来考虑什么时候需要翻转：当前i位置的值不是i时，考虑把i开始的长为k的区间翻转
然后考虑什么情况下无解：翻完第i个位置还不是i或者都翻了翻不动的位置不对
可以用一个数组模拟当前要不要翻长为k的区间，用一个数来标记顺序还是逆序（翻转偶数次还是奇数次）。
以i-1到i时，先从顺序的最左边把i-1拿走，此时需判断i-1的位置是否正确，然后判断当前最左的i需不需要翻转。
代码如下：
法一：
#include <iostream>
#include<algorithm>
using namespace std;
struct d{
int l,r,flag;
int qu[200010];
void reverse(){
flag^=1;
}
void push_back(int x){
if (flag == 0) qu[r++]=x;
else qu[--l]=x;
}
int front(){
if (flag == 0) return qu[l];
else return qu[r-1];
}
void pop_front(){
if (flag == 0) l++;
else r--;
}
}q;
int main(){
int n;
int a[100010];
int pos[100010];
cin>>n;
for (int i=1;i<=n;i++){
cin>>a[i];
pos[a[i]]=i;
}
int k=0;
for (int i=1;i<=n;i++){
if(i != pos[i]){
k = pos[i]-i+1;
break;
}
}
if (k==0){
cout <<"yes"<<endl<<"1";
return 0;
}
bool ans=1;
q.l=100000;q.r=100000;
for (int i=1;i<=k;i++)
q.push_back(a[i]);
for (int i=1;i<=n;i++){
if (q.front()!=i){
q.reverse();
if (q.front()!=i){
ans=0;
break;
}
}
q.pop_front();
q.push_back(a[i+k]);
}
if (ans) cout <<"yes"<<endl<<k;
else cout <<"no"<<endl;
return 0;
}
法二：
#include<iostream>
#include<algorithm>
#include<cstdio>
using namespace std;
int a[100010]={0};
int pos[100010]={0};
int main()
{
int n ;
cin>>n;
int k=1;
for(int i=1;i<=n;i++){
cin>>a[i];
pos[a[i]]=i;
}
for(int i=1;i<=n;i++){
if(i!=pos[i]){
k=pos[i]-i+1;
break;
}
}
for(int i=1;i<=n;i++){
if(a[i]!=i&&i+k-1<=n){
for(int j=1;j<=k/2;j++)
{
swap(a[i+j-1],a[i+k-j]);
}
}
if(a[i]!=i){
cout<<"no"<<endl;
return 0;
}
}
cout<<"yes"<<endl;
cout<<k<<endl;
return 0;
}
内容总结
以上是互联网集市为您收集整理的2021牛客寒假算法基础集训营2 F.牛牛与交换排序(双端队列翻转)全部内容，希望文章能够帮你解决2021牛客寒假算法基础集训营2 F.牛牛与交换排序(双端队列翻转)所遇到的程序开发问题。 如果觉得互联网集市技术教程内容还不错，欢迎将互联网集市网站推荐给程序员好友。
内容备注
版权声明：本文内容由互联网用户自发贡献，该文观点与技术仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请发送邮件至 gblab@vip.qq.com 举报，一经查实，本站将立刻删除。
内容手机端
扫描二维码推送至手机访问。