题意

　　给出一个排列，每次操作可以交换相邻的两个值。使用若干次该操作使得数组有序。

　　问操作是否唯一。

 

题解

　　操作唯一当且仅当最长上升子序列长度>=n - 1。

　　

1 #include 
     
       2 using namespace std; 3  4 int a[100010]; 5  6 int main() 7 { 8     int T; 9     for (scanf("%d", &T); T; T--)10     {11         int n;12         scanf("%d", &n);13         for (int i = 0; i < n; ++i)14             scanf("%d", &a[i]);15         vector
      
        v;16         v.push_back(a[0]);17         for (int i = 1; i < n; ++i)18             if (a[i] > v[v.size() - 1])19                  v.push_back(a[i]);20             else21             {22                 int l(0), r(v.size() - 1);23                 while (l < r)24                 {25                     int mid = (l + r) / 2;26                     if (a[i] > v[mid])27                         l = mid + 1;28                     else29                         r = mid;30                 }31                 v[l] = a[i];32             }33         if (v.size() >= n - 1)34             puts("Y");35         else36             puts("N");37     }38     39     return 0;40 }