[IOI2019]排列鞋子 题解

一架飞机 · 2021-09-01 11:34:09 · 题解

上面的巨佬把贪心过程和实现讲得很详细了，我就来总结一些技巧以及证明吧。

（设 (x,y) 表示这一对鞋子分别在原数组中的位置）

• 先不考虑一对鞋子内部的顺序（左右），可以最后单独算。

• 两个排列 a 表示原来鞋子摆放顺序，b 表示最终的排列方案（a，b 里装的是鞋子（一个鞋子一个数））。设 c[i] 为 a[i] 在 b 中的位置，d[i] 为 b[i] 在 a 中的位置。所以 c 的逆序对数 = d 的逆序对数。这里研究 c 的逆序对数就比研究 d 的逆序对数方便，因为 b 排列中，两个鞋鞋是放在一起的，只用研究一对相邻的数。

• 只用研究相邻的两对鞋子，因为如果不这样排，一定有相邻的两对鞋子逆序（模型：一个数列如果不是升序的，就一定存在相邻的两对鞋子）。只要证明：把相邻的逆序的鞋子对反转不会变差（具体可以看这位大佬的）

代码：

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
template<typename T>void read(T&x){
    x=0;char ch=getchar();bool f=0;
    while(!isdigit(ch))f|=ch=='-',ch=getchar();
    while(isdigit(ch))x=(x<<1)+(x<<3)+ch-'0',ch=getchar();
    x=f?-x:x;
}
const int M=2e5+5;
int a[M],del[M],nx[M][2],c[M],d[M];vector<int> b[M][2];
int cc[M]={0,1,5,3,4,6,2};
ll ans;
void solve(int l,int r){
    if(l>=r)return;
    int mid=(l+r)/2;solve(l,mid);solve(mid+1,r);
    ll preans=ans;
    for(int i=l;i<=mid;i++){
        int k=lower_bound(c+mid+1,c+r+1,c[i])-c-mid-1;
        ans+=k;
    }
    int la1=l,la2=mid+1;
    for(int i=l;i<=r;i++){
        if(la2>r||(la1<=mid&&c[la1]<c[la2]))d[i]=c[la1++];else d[i]=c[la2++];
    }
    for(int i=l;i<=r;i++)c[i]=d[i];
}
int main(){
    int n;read(n);n*=2;
    for(int i=1;i<=n;i++){
        read(a[i]);
        if(a[i]<0)b[-a[i]][0].push_back(i);
        else b[a[i]][1].push_back(i);
    }
    int la=1;
    for(int i=1,x,y,k;i<=n;i++){
        if(del[i])continue;
        if(a[i]<0)x=-a[i],y=0;
        else x=a[i],y=1;
        k=b[x][!y][nx[x][!y]++];
        nx[x][y]++;
        del[k]=1;
        if(y==0)c[la]=i,c[la+1]=k;
        else c[la]=k,c[la+1]=i;
        la+=2;
    }
    printf("%lld",ans);
    return 0;
}