bzoj2058: [Usaco2010 Nov]Cow Photographs(逆序對)

? ? ? 題目大意：給出n個數的序列，每次可以交換相鄰的兩個數，問把序列變成編號i在編號i+1左邊，編號1在編號n右邊(一個環)最少需要多少步。如：35421最少交換兩次變為34512。

? ? ? 一開始看到這題，只會O(n2)，后來仔細想了一下，妙啊，妙不可言。

? ? ? 首先我們求出逆序對，即為這個序列變成升序排列的最小次數，問題就在于23451這類的怎么求了。突然，靈稽一動，我們只要把1改成6，然后就可以算出23456的答案，即23451的答案。至于方法，就是我們通過原序列逆序對數量減去1產生的逆序對數量，然后加上給序列添加6產生的逆序對數量，就是23451的答案了。接下來同理，把2改成7，于是我們就可以遞推出34512的答案了，以此類推算出所有情況的答案。。。總結一下方法就是把上一次算出來的答案減去現在序列里最小數產生的逆序對數量，然后加上給序列添加最大數+1產生的逆序對數量。

? ? ? 顯然，序列里沒有一個數比最小數小(一句廢話>_<)，所以它產生的逆序對數量就是最小數的位置-1；顯然，序列里沒有一個數比最大數大(兩句廢話>_<)，所以最大數產生的逆序對數量就是這個數后面的數的數量，即n-最大數的位置，也就是ans[i]=ans[i-1]-(pos[i]-1)+(n-pos[i])，然后我們就輸出min(ans[i])就行啦。

? ? ? 妙啊，妙不可言

代碼如下：

uses math;
varn,i:longint;ans,sum:int64;a,b,c:array[0..1000000]of int64;procedure merge(l,m,r:longint);
varl1,m1,k,i:longint;
beginl1:=l;m1:=m+1;k:=l;while (l1<=m)and(m1<=r)dobeginif a[l1]<=a[m1] thenbeginb[k]:=a[l1];inc(l1);inc(k);endelsebeginb[k]:=a[m1];inc(m1);inc(k);ans:=ans+m-l1+1;end;end;while l1<=m dobeginb[k]:=a[l1];inc(l1);inc(k);end;while m1<=r dobeginb[k]:=a[m1];inc(m1);inc(k);end;for i:=l to r do a[i]:=b[i];
end;procedure sort(l,r:longint) ;
varmid:longint;
beginif l=r then exit;mid:=(l+r)>>1;sort(l,mid);sort(mid+1,r);merge(l,mid,r);
end;beginreadln(n);for i:=1 to n dobeginread(a[i]);c[a[i]]:=i;end;sort(1,n);sum:=ans;for i:=1 to n dobeginsum:=sum-(c[i]-1)+(n-c[i]);ans:=min(ans,sum);end;writeln(ans);
end.

?