自动搬运

查看原文

来自洛谷，原作者为

	xiaoxiaoxia 学习，就是发现自己越来越菜的过程。||天行健，君子以自强不息|| 最后在线时间：2025年7月31日17时3分

搬运于2025-08-24 22:41:09，当前版本为作者最后更新于2023-05-03 10:52:36，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

题目分析：

题目给定了 $N$ 名用户的积分，以及系统只会匹配积分差为 $K$ 的两名用户。现在需要计算最多有多少名用户在线寻找对手时，系统却一场对局都匹配不起来。

解题思路：

1. 用一个数组 $a$ 记录每个积分出现的次数。
2. 遍历数组，用贪心算法计算无法匹配的用户数。

解题步骤：

1. 读取输入，得到用户数量 $n$ 和积分差 $k$。
2. 遍历用户，读取每个用户的积分 $x$，并在数组 $a$ 中增加对应的计数。
3. 初始化无法匹配的用户数 $ans$ 为 $0$。
4. 如果 $k$ 等于 $0$，说明只有积分相同的用户才能匹配，遍历数组 $a$，统计有积分的用户数，输出结果并返回。
5. 遍历数组 $a$ 中的积分 $i$（$0$ 到 $\text{MAXN}-k$），对于每个积分 $i$，计算无法匹配的用户数：

• 如果$a_{i} < a_{i+k}$，说明积分差为 $k$ 的用户更多，将 $a_{i+k}$ 减去$a_{i}$。
• 否则，将 $a_{i+k}$ 置为 $0$。

6. 遍历数组 $a$ 中的积分 $i$（$0$ 到 $\text{MAXN}-k$），累加无法匹配的用户数。
7. 输出结果。

代码部分

#include<bits/stdc++.h>
using namespace std;
#define MAXN 100010
int a[MAXN];
int n, k, x;
int main()
{
	scanf("%d%d",&n,&k);
	for(int i=0;i<n;i++) 
	{
		scanf("%d",&x);
		a[x]++; 
	} 
	int ans=0;
	if(k==0) 
	{
		for(int i=0;i<MAXN;i++)
		{
			if(a[i]) 
			{
				ans++;
			}
		}
		printf("%d\n",ans);
		return 0;
	}
	for(int i=0;i<MAXN-k;i++) 
	{
		if( a[i]<a[i+k]) 
		{
			a[i+k]-=a[i];
		} 
		else 
		{
			a[i+k]=0;
		}
	}
	for (int i=0;i<MAXN-k;i++) 
	{
		ans+=a[i];
	}
	printf("%d\n",ans);
	return 0;
}