A40822. 对局匹配
填空题
困难
知识点
题目描述
对局匹配
题目描述
小明喜欢在一个围棋网站上找别人在线对弈。这个网站上所有注册用户都有一个积分，代表他的围棋水平。
小明发现网站的自动对局系统在匹配对手时，只会将积分差恰好是 K 的两名用户匹配在一起。
如果两人分差小于或大于 K，系统都不会将他们匹配。
现在小明知道这个网站总共有 N 名用户，以及他们的积分分别是 A1, A2, … AN。
小明想了解最多可能有多少名用户同时在线寻找对手，但是系统却一场对局都匹配不起来 (任意两名用户积分差不等于 K)？
输入格式
第一行包含两个个整数 N 和 K。
第二行包含N个整数 A1, A2, … AN。
输出格式
一个整数，代表答案。
样例输入1
10 0
1 4 2 8 5 7 1 4 2 8
样例输出1
6
样例输入2
10 1
2 1 1 1 1 4 4 3 4 4
样例输出2
8
参考答案
#include <iostream>
using namespace std;
const int N = 100010;
int n, k, x, ans;
int cnt[N], s[N], f[N];
int main()
{
cin >> n >> k;
for (int i = 1; i <= n; i ++)
{
cin >> x;
cnt[x] ++; // 统计每个积分出现的次数
}
if(k == 0) // k = 0 需要特判
{
for (int i = 0; i < N; i ++)
if(cnt[i]) ans ++;
}
else
{
for (int i = 0; i < k; i ++) // 分成 k 个公差为 k 的等差数列
{
int u = 0;
for (int j = i; j <= N; j += k) // 首项分别为 i 出现的次数
s[u ++] = cnt[j];
f[0] = s[0];
for (int j = 1; j < u; j ++)
{
if(j == 1) f[j] = max(f[j - 1], s[j]);
else f[j] = max(f[j - 1], f[j - 2] + s[j]);
}
ans += f[u - 1]; // 加上每组等差数列选择的最大值
}
}
cout << ans << endl;
return 0;
}
上一题
下一题