题解 P5749 【[IOI2019]排列鞋子】

· · 题解

题解：P5749 [IOI2019]排列鞋子

约定：下文统一用x和-x来表示鞋的大小，其中x>0。且-x表示左脚鞋，x表示右脚鞋。

思路：

第一步：从左向右遍历，对于每一个 x>0 的鞋，找到最左边的可以与它配对的鞋（是 -x 且没有与其他鞋配对），将两者配对。

（我们暂时只把两者标记为互相配对，具体计算和交换鞋子等操作在以后的步骤中）

解释：从左向右配对而每次找最左边的一定是最优解。如下图：显然绿色长度之和小于蓝色长度之和。也就是说，上文所述的策略实际上是避免了两个相距很远的鞋子互相配对。而且将其推广到所有情况，都成立。（严格数学证明可以参考其他题解）

第二步：再次从左向右遍历，每遇到一个没有操作过的鞋（不论左右脚鞋）就将与它配对的鞋换到它边上。并将两者标记为“操作过”。（这一步骤开始时，所有鞋都看作未操作过）

解释：设找到的鞋是 a，与 a 配对的鞋是 b 。因为是从左向右遍历，所以 a 和 b 相比一定更靠左，且只有 a 的右侧有 没有操作过的鞋 。把 b 换过来，相当于 a 的右侧少了一只鞋，且 a 和 b 不可能在没有没有操作鞋中间。使得对后面的交换而言，实际上就可以忽略 a 和 b ，而且也缩短了别的未操作的鞋子之间的距离。（否则，将 a 换到 b 处，则会导致后面的匹配交换次数增加）

第三步：在第二步的基础上计算移动次数。

代码实现：

第一步：使用链表（本文使用前向星，也可以使用 vector 或 STL 中的链表等）存储尺码为 x 的鞋的出现位置。那么即可实现 O(1) 查询到当前最左边的可配对的鞋。
开一个数组 b[] 存储每一只鞋它的搭档的位置。如 a 与 c （ a 与 c 为下标）配对，则 b[a]=c;b[c]=a
按照思路中说的遍历一遍，处理好b数组即可。

第二步：（将思路中的第二步与第三步结合）：参考思路中的第二步。显然不能真的去模拟交换的过程（显然超时）。将两只鞋移到一起的交换次数就等于两者下标之差。但是，根据上文可知，两只鞋之间的距离会因为先于它们的鞋的交换而改变，而且可以知道现在的两只鞋中间每有一只已经标记过的鞋，两者之间的距离就会少 1 。
使用树状数组维护未标记的鞋的前缀和，如果某只鞋（还有它的搭档）已经被标记，那么就树状数组单点修改（减1）即可。同时，树状数组可以一边遍历，一边统计答案。

具体细节看代码，时间复杂度在 O(n \ log_2 \ n) 左右。：

#include<bits/stdc++.h>
using namespace std;
const int e=(1e5)*4+10;
int n,a[e];
int cnt=0,head[e];//
struct nod//前向星 可以把它看成链表
{
    //可以通过head数组加上for循环来遍历每一个
    int next,pl;// pl 指的是当前访问到的鞋在原来数列中的下标，next则相当于指向下一个的指针
}s[e];
int b[e];//记录每一只鞋的对应鞋的下标
long long ans=0,tr[e];
//tr数组就是树状数组维护的部分
bool vis[e];//在第二步中保存 一只鞋是否操作过 的数组
void add(int x,int ii)
{
    cnt++;
    s[cnt].next=head[x];
    s[cnt].pl=ii;
    head[x]=cnt;
}
int lowbit(int x)
{
    return x&(-x);
}
void xg(int x,int va)//树状数组单点修改
{
    for(int i=x;i<=n;i+=lowbit(i))
    {
        tr[i]+=va;
    }
}
long long sum(int x)//树状数组区间求和
{
    long long res=0;
    for(int i=x;i>0;i-=lowbit(i))
    {
        res+=tr[i];
    }
    return res;
}
int main()
{
    cin>>n;
    n=n*2;//一共有 n 双 鞋。
     ans=0;
    for(int i=1;i<=n;i++)
    {
        cin>>a[i];
         a[i]+=n;//对负数进行处理，避免数组越界
     }
     for(int i=n;i>0;i--)
     {
         add(a[i],i);//由于前向星的特殊性质（后进入的先访问），为了下面方便的从左向右遍历，需要从后向前（倒序）存储
     }
    for(int i=1;i<=n;i++)
    {
        if(a[i]>n)//找到每个正数，找到它对应的负数。
        {
            int u=2*n-a[i];//注意：找到负数对应的值，别写错。
            int tmp=s[head[u]].pl;
            b[i]=tmp;b[tmp]=i;
            if(tmp>i)ans++;
            //假如负的鞋子在正的鞋子的右边，那么在正的和负的鞋子在交换到一起后还需要再一次交换（因为要求负的在左，正的在右）
            head[u]=s[head[u]].next;//修改最左边的与 i 能配对的 的鞋的位置，为下一次配对做准备。
        }
    }
    memset(vis,false,sizeof(vis));//全部标记为未操作
    for(int i=1;i<=n;i++)
    xg(i,1);//最开始，全部都没有操作过
    for(int i=1;i<=n;i++)
    {
        if(vis[i]==true)continue;
        long long tmp=sum(b[i]-1)-sum(i);//注意：当前鞋交换所需的次数是两者中间的鞋的个数（不包括两边当前的鞋）所以前缀和的下标要注意。
        //显然 b[i] 在 i 的后面，因为 i 先被遍历到
        ans+=tmp;
        vis[i]=true;vis[b[i]]=true;//标记为已操作
        xg(i,-1);xg(b[i],-1);//这两只鞋操作过以后，它们就不能在另外的操作中计算了（具体参考上文），所以要减掉。
    }
    cout<<ans;
    return 0;
}