P1966 [NOIP 2013 提高组] 火柴排队

首先题面中给出了两点之间的距离公式

（a[i]-b[i]）^2

然后我们拆解开来就可以变成

a[i]^2+b[i]^2-2*ai*bi

在处理的过程中，我们可以发现

a[i]^2+b[i]^2

的总值是不变的但是a[i]和b[i]的成绩会因为交换两根火柴的顺序而变化，按照排序不等式，最大的这个乘积和应当是顺序和，所以只需要处理其中一个的顺序即可

然后考虑a[i]和b[i]的配对，因为我们知道一个情况ai * bi求和的最大值，在有序情况下正序和>逆序和>乱序和（即排列不等式），所以我们要从小到大排列

但是本题不考方案得出的结果只考交换次数，而要让一个数组的序号变成另一个数组的序号，所以我们需要离散化，将每个数变成离散化后的序号要是他变成目标序号要每个相邻的交换于是这个问题就又转化成了用树状数组找逆序对的问题以样例为例 1
然后我们给它离散化就变成了
2 3 1 4
3 2 1 4的序号如果交换下面的3 2号，这样就可以使距离最小，即为位置的离散化
第二个样例也是如此

CPP

#include<bits/stdc++.h>
using namespace std;
#define int long long
const int maxn = 1e5+7;
const int mod = 1e8-3;
int n,c[maxn],t[maxn],ans;
struct Node{
	int id,v;
}a[maxn],b[maxn];
bool cmp(Node a,Node b) {
	return a.v<b.v;
}
int lowbit(int x) {
	return x&-x;
}
void modify(int x,int v) {
	while(x<=n) {
		t[x]+=v;
		x+=lowbit(x);
	}
}
int query(int x) {
	int sum=0;
	while(x>0) {
		sum+=t[x];
		x-=lowbit(x);
	}
	return sum;
}
signed main(){
	cin>>n;
	for(int i=1;i<=n;i++) {
		cin>>a[i].v,a[i].id=i;
	}
	for(int i=1;i<=n;i++) {
		cin>>b[i].v,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[b[i].id]=a[i].id;
    }
    for (int i=n;i>=1;i--) {
        ans += query(c[i]);
        modify(c[i], 1);
    }
    cout <<ans%mod<<"\n";
	return 0;
}

P1966 [NOIP 2013 提高组] 火柴排队

文章操作

相关推荐

评论

P1966 [NOIP 2013 提高组] 火柴排队