from : https://blog.csdn.net/sunmenggmail/article/details/8151793
用完全平方差公式将式子拆开后可以得出是求ai*bi得最大值
如果a<b,c<d 则a*d+b*c<a*c+b*d
所以要使得ai*bi最大，只需要a数组和b数组中最大值，次大值......一一对应
pos[i]记录的是在a数组中位置为i的数，它对应的（排序后位置一样的，即要求的值）在b数组中的位置，
这样只要pos升序排序就好了，但这排序有个限制，就是只能两两交换
现将最大值两两交换排到最后，删去，再将次大值两两交换排到最后，删去.....
其实交换次数就是求序列的逆序对的个数
如果说最小的话，就是这样避免了不必要的交换，比如将两个数列都按升序排序
还有就是在函数内不能开long long的数组
1 #include<iostream> 2 #include<cstdio> 3 #include<algorithm> 4 #include<cstring> 5 #include<cmath> 6 #include<vector> 7 #include<map> 8 #include<set> 9 #include<queue> 10 #include<stack> 11 using namespace std; 12 const int maxn=1e5+7; 13 const int mod=99999997; 14 typedef long long ll; 15 ll n,ans; 16 int pos[maxn]; 17 struct Node{ll v,num;}a[maxn],b[maxn]; 18 ll read(){ 19 ll f=1,x=0;char s=getchar(); 20 while(s<'0'||s>'9'){if(s=='-') f=-1;s=getchar();} 21 while(s>='0'&&s<='9'){x=x*10+s-'0';s=getchar();} 22 return x*f; 23 } 24 bool cmp(Node x,Node y){return x.v<y.v;} 25 void msort(ll l,ll r){ 26 if(l>=r) return; 27 ll mid=(l+r)/2; 28 msort(l,mid);msort(mid+1,r); 29 ll i=l,j=mid+1,k=l;int tmp[maxn]; 30 while(i<=mid&&j<=r){ 31 if(pos[i]>pos[j]){ 32 tmp[k++]=pos[j++]; 33 ans+=mid-i+1; 34 ans%=mod; 35 } 36 else tmp[k++]=pos[i++]; 37 } 38 while(i<=mid) {tmp[k++]=pos[i++];} 39 while(j<=r) {tmp[k++]=pos[j++];} 40 for(ll i=l;i<=r;i++) pos[i]=tmp[i]; 41 } 42 int main(){ 43 //freopen("a.in","r",stdin); 44 n=read(); 45 for(ll i=1;i<=n;i++) {a[i].v=read();a[i].num=i;} 46 for(ll i=1;i<=n;i++) {b[i].v=read();b[i].num=i;} 47 sort(a+1,a+n+1,cmp);sort(b+1,b+n+1,cmp); 48 for(ll i=1;i<=n;i++) pos[a[i].num]=b[i].num; 49 msort(1,n); 50 printf("%lld ",ans%mod); 51 return 0; 52 }