专栏文章

题解：P1966 [NOIP2013 提高组] 火柴排队

DDiaoHantong
P1966题解参与者 1已保存评论 0

文章操作

快速查看文章及其快照的属性，并进行相关操作。

当前评论
0 条
当前快照
1 份
快照标识符
@miqin84c
此快照首次捕获于
2025/12/04 05:25
3 个月前
此快照最后确认于
2025/12/04 05:25
3 个月前
查看原文

题目传送门

思路

首先观察要最小化的式子 ∑(ai−bi)2\sum (a_i-b_i)^2，由于 (ai−bi)2=ai2+bi2−2aibi(a_i-b_i)^2=a_i^2+b_i^2-2a_ib_i，所以有 ∑(ai−bi)2=∑(ai2+bi2−2aibi)=∑ai2+∑bi2−2∑aibi\sum(a_i-b_i)^2 =\sum(a_i^2+b_i^2-2a_ib_i)=\sum a_i^2+\sum b_i^2-2\sum a_ib_i。
由于 ∑ai2\sum a_i^2 和 ∑bi2\sum b_i^2 无论如何排列火柴都不会改变，所以问题转化为最大化 ∑aibi\sum a_ib_i。可以证明，把两个序列排序后，对每个 kk，将第 kk 小的 aka_k 元素与第 kk 小的 bkb_k 元素配对，这样得到的 ∑aibi\sum a_ib_i 是最大的。
然后考虑如何计算答案，可以发现在第 11 列交换和在第 22 列中交换是等价的，所以只考虑对一列进行交换。
首先排序，然后计算出两个数组 cic_i 和 did_i， cic_i 表示第 11 列中第 ii 个元素在第 11 列中是第 cic_i 大的， did_i 表示第 22 列中第 ii 个元素在第 22 列中是第 did_i 大的。由此，问题便转化为至少需要交换多少个相邻元素，使得 cic_i 序列变成 did_i 序列。
这里由于两个数组都是一个排列，所以可以先做一个映射，然后就用归并排序求逆序对就可以了。

代码

CPP
#include<bits/stdc++.h>
using namespace std;
const int N=1e5+1;
const int mod=1e8-3;
int a[N],b[N],c[N],d[N],r[N];
long long ans=0;
map<int,int> ai;
map<int,int> bi;
map<int,int> m;
void read(int &x){ 
	int f=1;x=0;char s=getchar();
	while(s<'0'||s>'9'){if(s=='-')f=-1;s=getchar();}
	while(s>='0'&&s<='9'){x=x*10+s-'0';s=getchar();}
	x*=f;
}
void msort(int left,int right){//归并排序求逆序对
    if(left==right)return;
    int mid=(left+right)/2;
    msort(left,mid);
    msort(mid+1,right);
    int i=left,j=mid+1,k=left;
    while(i<=mid&&j<=right){
        if(a[i]<=a[j]){
            r[k]=a[i];
            k++;
            i++;
        }else{
            r[k]=a[j];
            k++;
            j++;
            ans=(ans+mid-i+1)%mod;//记得取模
        }
    }
    while(i<=mid){
        r[k]=a[i];
        k++;
        i++;
    }
    while(j<=right){
        r[k]=a[j];
        k++;
        j++;
    }
    for(int i=left;i<=right;i++) a[i]=r[i];
}
int main(){
    int n;
    cin>>n;
    for(int i=1;i<=n;i++){
        read(a[i]);
        c[i]=a[i];//记录c[i]
        ai[a[i]]=i;
    }
    for(int i=1;i<=n;i++){
        read(b[i]);
        d[i]=b[i];//记录d[i]
        bi[b[i]]=i;
    }
    sort(c+1,c+1+n);
    sort(d+1,d+1+n);
    for(int i=1;i<=n;i++){
        b[bi[d[i]]]=i;
        a[ai[c[i]]]=i;
    }
    for(int i=1;i<=n;i++)m[b[i]]=i;//映射
	for(int i=1;i<=n;i++)a[i]=m[a[i]];
	msort(1,n);//求逆序对
	printf("%lld",ans%mod);
    return 0;
}

评论

共 0 条评论，欢迎与作者交流。

正在加载评论...