P9562 [SDCPC2023] G-Matching 题解

scp020 · 2023-08-18 22:52:55 · 题解

P9562 [SDCPC2023] G-Matching 题解

签到题，是这场比赛第三简单的题。

解法

题中说对于 i - j = a_i - a_j，我们从 i 到 j 连一条边权为 a_i + a_j 的双向边。

对于这个式子，我们可以变形为 a_i - i = a_j - j，而且不难发现如果有一些数它们的 a_i - i 都相同，则这些数互相之间都有连边。整张图会分为若干连通块（或孤立点），每个连通块内都是一个完全图。现在问题转化为求完全图的最大权匹配。

我们考虑在输入 a_i 时将 a_i 转化为 a_i - i 存储，记为 val_i，这样 a_i 可表示为 val_i + i。然后将所有点将 val 作为第一关键字，将 i 作为第二关键字降序排序。这样一段连续的 val 相同的区间即为一个连通块。如果一个连通块内有奇数个点，我们就舍去 a_i 最小的点，剩下的点两两匹配，如果有偶数个点，我们就两两匹配。注意，如果两两匹配时 a_i + a_j < 0，我们就舍弃这两个点。

代码

#include<bits/stdc++.h>
using namespace std;
namespace fast_IO
{
    /*
    快读快写，可忽略。
    */
};
using namespace fast_IO;
#define int long long
int t,n;
int ans;
struct node
{
    int pos,val;
};
node a[100010];
inline bool cmp(const node &x,const node &y)
{
    if(x.val==y.val) return x.pos>y.pos;
    return x.val>y.val;
}
signed main()
{
    read(t);
    while(t--)
    {
        read(n),ans=0;
        for(int i=1;i<=n;i++) read(a[i].val),a[i].val-=i,a[i].pos=i;
        sort(a+1,a+n+1,cmp);
        for(int i=2,cnt=1;i<=n;i++)
        {
            if(a[i].val!=a[i-1].val)
            {
                cnt=1;
                continue;
            }
            if(cnt&1) ans+=max(a[i].val+a[i-1].val+a[i].pos+a[i-1].pos,0ll);
            cnt++;
        }
        write(ans),Putchar('\n');
    }
    fwrite(Ouf,1,p3-Ouf,stdout),fflush(stdout);
    return 0;
}