Sort the Array

1 /*
 2    思路： 
 3    找到单调下降串的起始位置[l, r]
 4    如果左边 0...l-1中的最大值 > l...r中的最小值 或者
 5    r+1...n中的最小值 < l...r中的最大值 都是不能实现排序的！ 
 6 */
 7 #include<iostream>
 8 #include<cstdio>
 9 #include<algorithm>
10 using namespace std;
11 typedef long long LL;
12 int cur, nt;
13 int cnt;
14 int num[100005];
15 int main(){
16    int i, n;
17    int begin, end;
18    int flag;
19    int min1, max2;
20    while(scanf("%d", &n)!=EOF){
21           cnt=cur=0;
22        flag=0;
23        for(i=1; i<=n; ++i){
24           scanf("%d", &nt);
25           num[i]=nt;
26           if(nt>cur)
27              flag=0;
28           if(!flag && nt<cur){
29              ++cnt;
30              flag=1;
31              begin=i-1;
32              end=i;
33           }
34           if(flag && nt<cur)
35                end=i;
36           cur=nt;
37        }
38       if(cnt==1){
39            min1=0x3f3f3f3f;
40            if(end!=n)
41                min1=num[end+1];
42          max2=-0x3f3f3f3f;
43          if(begin!=1)
44              max2=num[begin-1];
45          if(max2>num[end] || min1<num[begin]) 
46             printf("no\n");
47          else
48             printf("yes\n%d %d\n", begin, end);
49       }
50       else if(cnt==0)
51          printf("yes\n1 1\n");
52       else printf("no\n");
53    }
54    return  0;
55 }

 1 /*
 2 思路：
 3    将两边单调递增的序列排除（将元素和元素下标一一映射起来，排序之后找到元素和下标映射不同的两个端点），然后中间的那部分就是要翻转的！
 4 最后检查翻转部分的元素和下标是否对应！

 5    
 6 */
 7 #include<iostream>
 8 #include<algorithm>
 9 #include<map>
10 #include<cstdio>
11 #define M 100005
12 using namespace std; 
13 int n;
14 int a[M], b[M]; 
15 map<int, int>mp;
16 int main(){
17    int i;
18    while(cin>>n){
19       for(i=0; i<n; ++i){
20          cin>>a[i];
21          b[i]=a[i];
22       }
23       sort(a, a+n);
24       for(i=0; i<n; ++i)
25         mp[b[i]]=i;
26       for(i=0; i<n; ++i)
27         a[i]=mp[a[i]];
28       int L=-1, R=-1;
29       for(i=0; i<n; ++i)
30          if(a[i]!=i){
31             L=i;
32             break;
33          } 
34       for(i=n-1; i>=0; --i)
35          if(a[i]!=i){
36             R=i;
37             break;
38          } 
39        int ok=1;
40        if(L==-1 || R==-1)
41           cout<<"yes"<<endl<<"1 1"<<endl;
42        else{
43           reverse(a+L, a+R+1);
44           
45           for(i=L; i<=R; ++i){
46              if(a[i]!=i){
47                 ok=0;
48                 cout<<"no"<<endl;
49                 break;
50              }
51           } 
52           
53           if(ok)
54             cout<<"yes"<<endl<<L+1<<" "<<R+1<<endl; 
55        } 
56    } 
57    return 0;
58 }