[IOI2019]排列鞋子
zhouhuanyi
·
·
题解
链接:https://www.luogu.com.cn/problem/P5749
题目描述:
将一个序列$A$交换到满足对于任意的$i(1<=i<=n/2)$满足
$a_{i}=-a_{i\times 2}$且$a_{i}<0$,求至少要交换多少次。
题解:交换多少次就等价于交换得到的排列的逆序对数量,我们可以从这构造一个这样的排列入手。
引理$1$:每一组$a_{i}$相同的左脚鞋与右脚鞋匹配时,从小到大依次匹配最优。
证明:对于每一组匹配$(i,j)$,其贡献为剩余的满足$[k<=i]$的与满足$[k<=j]$的和。因为我们每一次一定是贪心的选取两个贡献最少的,所以每一次要求出满足
$[k<=i]+[k<=j]$的最小$(i,j)$。考虑反证:假设我们选取$a_{i}$相同的不依次匹配的数对$(i,j)$更优,令$a_{i}$依次匹配时$i$匹配了$t$,则$t<=j$。那么$[k<=i]+[k<=t]<=[k<=i]+[k<=j]$,则答案此时便的更劣了,矛盾,则该假设不成立。
引理$2$:按照引理$1$匹配之后,令$b_{i}$表示左脚鞋$i$匹配的数,则以$min(a_{i},a_{b_{i}})$按顺序排列更优。
证明:~~不会,打表吧~~。
根据上述引理:我们可以将逆序对最小的排列求出,树状数组求该排列的逆序对即可。
```
#include<iostream>
#include<set>
#include<queue>
#include<algorithm>
using namespace std;
struct node
{
int l,r;
bool operator < (const node &t)const
{
return min(l,r)<min(t.l,t.r);
}
};
node t[1000001];
vector<int>s[1000001];
int n,a[1000001],len,d[2000001];
long long c[1000001],S,ans;
int lowbit(int x)
{
return x&(-x);
}
void add(int x,int y)
{
for (;x<=n;x+=lowbit(x))
c[x]+=y;
return;
}
long long sum(int x)
{
S=0;
for (;x>=1;x-=lowbit(x))
S+=c[x];
return S;
}
int main()
{
cin>>n;
n*=2;
for (int i=1;i<=n;++i)
{
cin>>a[i];
if (a[i]<0)
s[-a[i]].push_back(i);
}
for (int i=n;i>=1;--i)
{
if (a[i]>0)
{
t[++len].l=s[a[i]][s[a[i]].size()-1];
s[a[i]].pop_back();
t[len].r=i;
}
}
sort(t+1,t+n/2+1);
for (int i=1;i<=n/2;++i)
{
d[i*2-1]=t[i].l;
d[i*2]=t[i].r;
}
for (int i=1;i<=n;++i)
{
ans+=sum(n+1-d[i]);
add(n+1-d[i],1);
}
cout<<ans<<endl;
return 0;
}