I - Inverted Deck（思维题）

本文主要是介绍I - Inverted Deck（思维题），希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

题目


题意：给出n个数，若能交换其中的一段数序列使之能从小到大排列。输出改变的左端点和右端点的下标值；否则输出-1；
思路：sort一遍使序列成为从小到大的排列，与原串对比查找;
1特判与原串相同输出“1 1”；
2特判从大到小的情况输出“1 n”;
3剩余的情况：left从1开始找不相等的左端点，right从n开始倒着找不相等的右端点；swap （left,right)的序列；若swap与原串相同输出“left right”；否则输出“-1”；

AC代码

#include <bits/stdc++.h>using namespace std;
int a[1000010];
int b[1000010];
int main()
{int n;cin>>n;for(int i=1; i<=n; i++){cin>>a[i];b[i]=a[i];}sort(b+1,b+1+n);int flag=1;if(flag==1){for(int i=1; i<=n; i++){if(a[i]!=b[i]){flag=0;break;}}}if(flag==1)//从小到大的情况{cout<<1<<" "<<1<<endl;}else{int g=1;for(int i=1; i<=n; i++){if(a[i]!=b[1+n-i]){g=0;break;}}if(g==1)//从大到小的情况cout<<1<<" "<<n<<endl;else//一般情况{int right=n,left=1;for(int i=1; i<=n; i++){if(a[i]==b[i]){left++;}else{break;}}for(int i=n; i>=1; i--){if(a[i]==b[i]){right--;}elsebreak;}for(int j=left; j<=(left+right)/2; j++){swap(a[j],a[left+right-j]);}int flag=1;for(int i=1; i<=n; i++){if(a[i]!=b[i]){flag=0;break;}}if(flag==1)cout<<left<<" "<<right<<endl;elsecout<<"impossible"<<endl;}}return 0;
}

这篇关于I - Inverted Deck（思维题）的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---