题目链接：

题意：

　　给你一个由1~n组成的排列，首尾相接围成一个环。

　　你可以任意次交换其中两个相邻位置的数字。

　　最终你要让所有数字顺时针递增，只有n顺时针紧邻着1。

　　问你最小的交换次数。

 

题解：

　　举个例子。

　　有一个由1~5组成的环：2 3 1 4 5

　　对于这个环，最终答案有若干种情况：

　　　　（1）1 2 3 4 5

　　　　（2）2 3 4 5 1

　　　　（3）3 4 5 1 2

　　　　（4）4 5 1 2 3

　　　　（5）5 1 2 3 4

　　每一次变化，无非是分别将1~4移到了最右边。

　　对于从（1）到（2）的变化，其实就是将原环中的1改为了一个比其他都大的数字（比如6），然后求了一遍逆序对。

　　对应到最终结果中，也就是1变成了最右边的数。

 

　　所以变化之后的答案 = 上一次的答案 - 数字i所贡献的逆序对个数 + 改成的更大的数所贡献的逆序对个数

 

　　对于每一次将数字i改为更大的数时，i一定是当前环中最小的数字。

　　令pos[i]为数字i在原环中出现的位置(1 <= pos <= n)。

　　所以：

　　　　i贡献的逆序对 = pos[i] - 1

　　　　更大的数贡献的逆序对 = n - pos[i]

　　即：res = res - 2*pos[i] + 1 + n

　　

　　对于所有res取最小即可。

 

AC Code:

1 #include 
     
       2 #include 
      
        3 #include 
       
         4 #define MAX_N 100005 5 #define INF 1000000000 6  7 using namespace std; 8  9 int n;10 int a[MAX_N];11 int l[MAX_N];12 int r[MAX_N];13 int dat[MAX_N];14 int pos[MAX_N];15 long long ans=0;16 long long res=0;17 18 void read()19 {20     cin>>n;21     for(int i=1;i<=n;i++)22     {23         cin>>a[i];24         pos[a[i]]=i;25     }26 }27 28 void merge(int lef,int mid,int rig)29 {30     int n1=mid-lef+1;31     int n2=rig-mid;32     for(int i=0;i