http://acm.hust.edu.cn/vjudge/problem/viewProblem.action?id=52107
给出一个数列，问截取哪一部分连续子列进行翻转可以使整个数列升序排列，
如果有这样的字串输出yes和截取位置，没有输出no
就是先记录原始位置进行排序，之后一旦发现一个元素排序后更改了位置那它就被翻转过。
完全逆序排列应该是排序后原先的位置依次减1，这样得到被翻转的前后位置。
之后继续扫描，如果还有位置不对的，说明翻转一段不能完成，输出no
1 #include<bits/stdc++.h> 2 using namespace std; 3 #define LEN 100005 4 typedef struct point{ 5 int a, p; 6 bool operator < (const point& p) const{ 7 return a < p.a; 8 } 9 }point; 10 point arr[LEN]; 11 12 int main(){ 13 int n; 14 while(~scanf("%d", &n)){ 15 memset(arr, 0, sizeof(arr)); 16 for(int i = 1; i <= n; i++){ 17 scanf("%d", &arr[i].a); 18 arr[i].p = i; 19 } 20 sort(arr+1, arr+1+n); 21 int lpos = 1, rpos = 1; 22 bool f = true; 23 for(int i = 1; i <= n; i++) 24 if(arr[i].p != i){ 25 lpos = i; 26 rpos = i; 27 break; 28 } 29 for(int i = lpos+1; i <= n; i++){ 30 if(arr[i].p == arr[i-1].p-1) rpos = i; 31 else break; 32 } 33 for(int i = rpos+1; i <= n; i++) 34 if(arr[i].p != i){ 35 f = false; 36 break; 37 } 38 if(f == false) puts("no"); 39 else{ 40 puts("yes"); 41 printf("%d %d\n", lpos, rpos); 42 } 43 } 44 return 0; 45 }
【模拟】【codeforces】451B Sort the Array
原文：http://www.cnblogs.com/miaowTracy/p/5385172.html