题目lk
Day1T2一般都是贪心DP玄学题什么的
然后这题DP显然不怎么靠谱,因为位置可以随便换。。。
玄学方法窝也不会,只好写贪心。
然后简单找一下规律,发现一列顺序,一列降序即可
如果我们只有两个元素,$a_{1}$和$a_{2}$,以及$b_{1}$和$b_{2}$
好我们考虑$a_{1}<a_{2}$而$b_{2}<b_{1}$的情况(这种情况是正解)
这时候答案是$(a_{1}-b_{2})^{2}+(a_{2}-b_{1})^{2}$
同理另外一个(即$b_{1}<b_{2}$)是$(a_{1}-b_{1})^{2}+(a_{2}-b_{2})^{2}$
我们用前者减掉后者
于是经过眼花缭乱的化简,得到$(a_{1}-a_{2})(b_{1}-b_{2})$
要使得这个式子小于零(因为我们要让正解更小)
这两组差的符号就要不同
那末大小关系必然相反,所以推广到任意两个,可以得到一个数列升序,另一个降序
然后先给两个序列升序排好,记录相对位置(a中第i大元素在b中的位置),把相对位置统计一下逆序对即可
上代码
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<cstdlib>
#include<cmath>
#define maxn 100000+500
#define mod 99999997
using namespace std;
int n,ans=0,t[maxn];
int c[maxn];
struct node
{
int data,id;
}a[maxn],b[maxn];
void msort(int l,int r)
{
if (l==r) return;
int mid=((l+r)>>1);
msort(l,mid); msort(mid+1,r);
int p1=l,p2=mid+1,p3=l;
while (p1<=mid && p2<=r)
if (c[p1]<=c[p2])
t[p3++]=c[p1++];
else
{
t[p3++]=c[p2++];
ans=(ans+mid-p1+1)%mod;
}
while (p1<=mid) t[p3++]=c[p1++];
while (p2<=r) t[p3++]=c[p2++];
for (int i=l;i<=r;++i) c[i]=t[i];
}
int cmp(node x,node y)
{
return x.data<y.data;
}
int main()
{
scanf("%d",&n);
for (int i=1;i<=n;++i) scanf("%d",&a[i].data),a[i].id=i;
for (int i=1;i<=n;++i) scanf("%d",&b[i].data),b[i].id=i;
sort(a+1,a+1+n,cmp);
sort(b+1,b+1+n,cmp);
for (int i=1;i<=n;++i)
c[a[i].id]=b[i].id;
msort(1,n);
printf("%d",ans);
return 0;
}
转载于:https://www.cnblogs.com/hojqvfna-tcl/p/10657577.html