建站下载专用网站,网站开发流程说明,网站分成比例系统怎么做,wordpress博客无法评论题目大意#xff1a;给出n个数的序列#xff0c;每次可以交换相邻的两个数#xff0c;问把序列变成编号i在编号i1左边#xff0c;编号1在编号n右边(一个环)最少需要多少步。如#xff1a;35421最少交换两次变为34512。 一开始看到这题#xff0c;只会O(n)#xff0c;后来… 题目大意给出n个数的序列每次可以交换相邻的两个数问把序列变成编号i在编号i1左边编号1在编号n右边(一个环)最少需要多少步。如35421最少交换两次变为34512。 一开始看到这题只会O(n²)后来仔细想了一下妙啊妙不可言。 首先我们求出逆序对即为这个序列变成升序排列的最小次数问题就在于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:m1;k:l;while (l1m)and(m1r)dobeginif a[l1]a[m1] thenbeginb[k]:a[l1];inc(l1);inc(k);endelsebeginb[k]:a[m1];inc(m1);inc(k);ans:ansm-l11;end;end;while l1m dobeginb[k]:a[l1];inc(l1);inc(k);end;while m1r 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 lr then exit;mid:(lr)1;sort(l,mid);sort(mid1,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. View Code 转载于:https://www.cnblogs.com/Sakits/p/5837039.html
