Sort the Array-白红宇

1 /* 2    思路：  3    找到单调下降串的起始位置[l, r] 4    如果左边 0...l-1中的最大值 > l...r中的最小值 或者 5    r+1...n中的最小值 < l...r中的最大值 都是不能实现排序的！  6 */ 7 #include
     
       8 #include
      
        9 #include
       
        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
        
         num[end] || min1

1 /* 2 思路： 3    将两边单调递增的序列排除（将元素和元素下标一一映射起来，排序之后找到元素和下标映射不同的两个端点），然后中间的那部分就是要翻转的！ 4 最后检查翻转部分的元素和下标是否对应！  5     6 */ 7 #include
      
        8 #include
       
         9 #include
        10 #include
         
          11 #define M 10000512 using namespace std; 13 int n;14 int a[M], b[M]; 15 map
          
           mp;16 int main(){17    int i;18    while(cin>>n){19       for(i=0; i
           
            >a[i];21 b[i]=a[i];22 }23 sort(a, a+n);24 for(i=0; 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"<
             
              <<"1 1"<

本文转自小眼儿博客园博客，原文链接：http://www.cnblogs.com/hujunzheng/p/3885952.html，如需转载请自行联系原作者