ABC277D 题解

__vector__ · 2022-11-13 13:48:57 · 题解

题外话

不知道为啥别人都用的并查集。
我赛时写的记忆化搜索过去的。

做法

把题目画出来，就是所有 x 都可以互相到达，并且 x 可以到达 (x+1) \mod m。

然后现在我们要让剩下的值最少，转化一下就是让选择的数字总值最大，其实就是找一条路径，使得路径权值和最大。

我们进行建边，首先所有相同数字都可以互相到达，到达了一个数，就可以走到其他所有相同的数。

所以基于尽可能多选的贪心，我们可以把相同的数缩成一个点。

缩完点之后，将每个数组中出现过的数 x 连向 (x+1) \mod m。

然后依次枚举从 a_i 出发，进行爆搜。

爆搜的时候把答案记一下就行了，就是记忆化。

复杂度 O(n \log n)。
那个 log 是 map 的。
用 unordered_map 可以 O(n)。

Code

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn=2e5+5;
int n,m;
ll a[maxn];
map<ll,ll> cnt;
map<ll,bool> vis;
map<ll,ll> ans;
void dfs(ll num)
{
    if(cnt.find(num)==cnt.end())
    {
        return;
    }
    if(vis.find(num)!=vis.end())
    {
        return;
    }
    vis[num]=1;
    dfs((num+1)%m);
    ans[num]=ans[(num+1)%m]+cnt[num];
//  printf("ans[%d]: %d\n",num,ans[num]);
}
int main()
{
    ll sum=0;
    scanf("%d%d",&n,&m);
    for(int i=1;i<=n;i++)
    {
        scanf("%lld",&a[i]);
        sum+=a[i];
        cnt[a[i]]++;
    }
    sort(a+1,a+n+1);
    n=unique(a+1,a+n+1)-a-1;
    for(int i=1;i<=n;i++)
    {
        cnt[a[i]]=cnt[a[i]]*a[i];
    }
    for(int i=1;i<=n;i++)
    {
        if(vis.find(a[i])==vis.end())
        {
            dfs(a[i]);
        }
    }
    ll out=0;
    for(int i=1;i<=n;i++)
    {
        out=max(out,ans[a[i]]);
    }
    printf("%lld",sum-out);
    return 0;
}