本文章由 WyOJ Shojo 从洛谷专栏拉取，原发布时间为 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;
}