首页 > 代码库 > bzoj2058: [Usaco2010 Nov]Cow Photographs(逆序对)
bzoj2058: [Usaco2010 Nov]Cow Photographs(逆序对)
题目大意：给出n个数的序列，每次可以交换相邻的两个数，问把序列变成编号i在编号i+1左边，编号1在编号n右边(一个环)最少需要多少步。如：35421最少交换两次变为34512。
一开始看到这题，只会O(n²)，后来仔细想了一下，妙啊，妙不可言。
首先我们求出逆序对，即为这个序列变成升序排列的最小次数，问题就在于23451这类的怎么求了。突然，灵稽一动，我们只要把1改成6，然后就可以算出23456的答案，即23451的答案。至于方法，就是我们通过原序列逆序对数量减去1产生的逆序对数量，然后加上给序列添加6产生的逆序对数量，就是23451的答案了。接下来同理，把2改成7，于是我们就可以递推出34512的答案了，以此类推算出所有情况的答案。。。总结一下方法就是把上一次算出来的答案减去现在序列里最小数产生的逆序对数量，然后加上给序列添加最大数+1产生的逆序对数量。
显然，序列里没有一个数比最小数小(一句废话>_<)，所以它产生的逆序对数量就是最小数的位置-1；显然，序列里没有一个数比最大数+1大(两句废话>_<)，所以最大数产生的逆序对数量就是这个数后面的数的数量，即n-最小数的位置，也就是ans[i]=ans[i-1]-(pos[i]-1)+(n-pos[i])，然后我们就输出min(ans[i])就行啦。
妙啊，妙不可言
代码如下：
uses math;var n,i:longint; ans,sum:int64; a,b,c:array[0..1000000]of int64;procedure merge(l,m,r:longint);var l1,m1,k,i:longint;begin l1:=l;m1:=m+1;k:=l; while (l1<=m)and(m1<=r)do begin if a[l1]<=a[m1] then begin b[k]:=a[l1]; inc(l1);inc(k); end else begin b[k]:=a[m1]; inc(m1);inc(k); ans:=ans+m-l1+1; end; end; while l1<=m do begin b[k]:=a[l1];inc(l1);inc(k); end; while m1<=r do begin b[k]:=a[m1];inc(m1);inc(k); end; for i:=l to r do a[i]:=b[i];end;procedure sort(l,r:longint) ;var mid:longint;begin if l=r then exit; mid:=(l+r)>>1; sort(l,mid); sort(mid+1,r); merge(l,mid,r);end;begin readln(n); for i:=1 to n do begin read(a[i]); c[a[i]]:=i; end; sort(1,n); sum:=ans; for i:=1 to n do begin sum:=sum-(c[i]-1)+(n-c[i]); ans:=min(ans,sum); end; writeln(ans);end.
bzoj2058: [Usaco2010 Nov]Cow Photographs(逆序对)
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。