网站快照回档河南旅游网站建设

 题意：给两列火柴，可以交换任意相邻的火柴，使得（ai-bi)^2的和最小，求最小交换次数。

分析：使得（ai-bi)^2的和最小，即a^2-2ab+b^2的和最小，那么使得2ab最大，就可以使得整体最小。我们可以假设当序列有序时候，2ab最大。

假如a>b,c>d  ,那么ac+bd>ad+bc;

反证法：令ac+bd<ad+bc,那么c(a-b)<d(a-b),得出c<d，与事实不符，所以结论错误，即ac+bd>ad+bc，当序列有序时候，2ab最大。

此时问题就可以变为当序列有序时候，最小的交换次数怎么求

显然，把两个序列都从小到大，或者从大到小排列，显然交换次数不是最小的。

那么，可以求  a相对于b，把a排成和b大小关系一一对应的序列，即a序列的第一小和b序列的第一小在同一位置上，这样的交换次数是最少的。只需要 a队伍中第 i个数和 b队伍中第 i个数一一对应，那么就算两个队伍不是有序的也不影响结果。

所以我们可以存一下a，b序列的下标和数值，进行一下按值排序，就可以得到a，b的相对位置，此时可以增加一个数组c，c的下标存a数组的下标，c数组的值存b数组的下标，因为c数组下标是有序的，那么我们只要想到怎么使c数组的数值排序，使得数值也变成有序的就可以得到答案。

此时数值变成有序后，就表示a数组和b数组的大小关系变成了一一对应。

怎样变换可以想到树状数组或者逆序对。

#include<bits/stdc++.h>using namespace std;const int N = 1e5 + 10 , mod=99999997;
int n;
struct node
{int v,p;bool operator < (const node &w) const{return v<w.v;} 
}a[N],b[N];int tr[N];
int c[N];int lowbit(int x) 
{return x&(-x);
}
int query(int x)
{int res=0;for(int i=x;i>=1;i-=lowbit(i)) res+=tr[i];return res; 
}
void modify(int x,int c)
{for(int i=x;i<=n;i+=lowbit(i)) tr[i]+=1;
}int main()
{cin>>n;for(int i=1;i<=n;i++) cin>>a[i].v,a[i].p=i;for(int i=1;i<=n;i++) cin>>b[i].v,b[i].p=i;sort(a+1,a+n+1);sort(b+1,b+n+1);for(int i=1;i<=n;i++)  c[a[i].p]=b[i].p;int res=0;for(int i=n;i>=1;i--){res = (res+query(c[i]))%mod;modify(c[i],1);}cout<<res<<endl;return 0;
}