Farmer John希望给他的N(1<=N<=100,000)只奶牛拍照片,这样他就可以向他的朋友炫耀他的奶牛.这N只奶牛被标号为1..N.
在照相的那一天,奶牛们排成了一排.其中第i个位置上是标号为c_i(1<=c_i<=N)的奶牛.对于奶牛的站位,Farmer John有他自己的想法.
FJ是这么想的,标号为i(1<=i<=n-1)的奶牛只能站在标号为i+1的奶牛的左边,而标号为N的奶牛只能站在标号为1的奶牛的左边.当然,没有牛可以站在队列中最左边的奶牛的左边了.也就是说,最左边的奶牛编号是随意的.
这些奶牛都非常的饿,急切的希望吃到FJ承诺的在拍照后的大餐,所以FJ想尽快的拍照.奶牛们的方向感非常的不好,所以FJ每一分钟只可以选择相邻的两只奶牛然后让他们交换位置.FJ最小需要多少时间就能使奶牛站成一个可以接受的序列?
比方说一个有5只奶牛的例子,一开始序列是这样的:
左边 右边
3 5 4 2 1
第一分钟,FJ可以交换第二队奶牛(即5和4),交换后的队列:
3 4 5 2 1
第二分钟,FJ交换最右边的一对,序列变成这样:
3 4 5 1 2
这样,只用了2分钟,就是序列变为了一个FJ所希望的序列.
解题过程:刚写这道题时，没有看到题目中的"相邻"两个字，于是当成了置换来做，找使循环节最多的序列，一时间没想到什么办法，敲了个暴力交了一下，发现wa了，重新读题后发现了题目中有"相邻"两个字;
由于每次相邻的两个数字交换，每次交换一定会使逆序对数减小或增加1，可以证明最小的移动次数是逆序对数，然后就可以O(nlogn)，求一个序列的逆序对数；
但是最左端的数字不确定，考虑一下如果顺序变化序列对逆序对数有什么影响，可以让每个数加1，如果这个数是n，则变成1这样的顺序来变换序列；
这样很容易看出，其他数字+1对逆序对数没影响，只有n变成1这个变化会对逆序对数造成影响，然后就可以O(n)的复杂度顺序转移；
代码：
#include<iostream> #include<cstring> #include<cstdio> #include<cstdlib> #include<algorithm> #include<iomanip> #include<map> #include<set> #include<vector> #include<ctime> #include<cmath> #define LL long long using namespace std; #define LL long long #define up(i,j,n) for(int i=(j);(i)<=(n);(i)++) #define max(x,y) ((x)<(y)?(y):(x)) #define min(x,y) ((x)<(y)?(x):(y)) #define FILE "1" namespace OI{ const int maxn=101000; int n,a[maxn],b[maxn]; void init(){ scanf("%d",&n); up(i,1,n)scanf("%d",&a[i]); up(i,1,n)b[a[i]]=i; } bool vis[maxn]; int c[maxn]; int lowbit(int x){return x&-x;} int sum(int x){int ans=0;while(x>0)ans+=c[x],x-=lowbit(x);return ans;} void add(int x){while(x<=n)c[x]+=1,x+=lowbit(x);} LL get(){ LL ans=0; up(i,1,n){ ans+=sum(n-a[i]+1); add(n-a[i]+1); } return ans; } void work(){ LL ans=get(); LL minn=ans; for(int i=n;i>=1;i--){ ans=ans+2*b[i]-n-1; minn=min(ans,minn); } cout<<minn<<endl; } void slove(){ init(); work(); } } int main(){ using namespace OI; slove(); }