【洛谷 P8656】[蓝桥杯 2017 国 B] 对局匹配 题解（映射+位集合+贪心算法）

[蓝桥杯 2017 国 B] 对局匹配

题目描述

小明喜欢在一个围棋网站上找别人在线对弈。这个网站上所有注册用户都有一个积分，代表他的围棋水平。

小明发现网站的自动对局系统在匹配对手时，只会将积分差恰好是 $K$ 的两名用户匹配在一起。如果两人分差小于或大于 $K$，系统都不会将他们匹配。

现在小明知道这个网站总共有 $N$ 名用户，以及他们的积分分别是 $A_1,A_2,\cdots A_N$。

小明想了解最多可能有多少名用户同时在线寻找对手，但是系统却一场对局都匹配不起来（任意两名用户积分差不等于 $K$）？

输入格式

第一行包含两个个整数 $N$ 和 $K$。

第二行包含 $N$ 个整数 $A_1,A_2,\cdots ,A_N$。

输出格式

一个整数，代表答案。

样例 #1

样例输入 #1

10 0
1 4 2 8 5 7 1 4 2 8

样例输出 #1

6

样例 #2

样例输入 #2

10 1
2 1 1 1 1 4 4 3 4 4

样例输出 #2

8

提示

对于 $30\%$ 的数据，$1\le N\le 10$。

对于 $100\%$ 的数据，$1\le N\le 10^5$，$0\le K,A_i\le 10^5$
。

时限 1 秒, 256M。蓝桥杯 2017 年第八届国赛

思路

首先从输入中读取两个整数 n 和 k，分别表示用户数量和积分差。然后定义一个 bitset valid 和一个 map m1。bitset valid 用于标记某个积分的用户是否存在，map m1 用于存储每个积分的用户数量。

接着对于每个用户，从输入中读取其积分 t，并在 map m1 中将 t 作为键，对应的值增加 1。同时，将 bitset valid 中的 t 位置为 1，表示存在积分为 t 的用户。

如果 k 等于 0，表示系统只会将积分相同的用户匹配在一起。此时，输出 valid.count()，即积分种类数，就是系统一场对局都匹配不起来的用户数量。

如果 k 不等于 0，需要将积分差恰好是 k 的两名用户匹配在一起。对于 map m1 中的每一对键值对 i，如果 valid[i.first + k] 为真并且 m1[i.first + k] 大于 0，表示存在积分差为 k 的用户。

当 m1[i.first] 大于或等于 m1[i.first + k] 时，积分为 i.first 的用户数量足够与积分为 i.first + k 的所有用户进行匹配。在这种情况下，积分为 i.first + k 的用户都可以找到积分差为 k 的对手，他们不是系统匹配不起来的用户。因此，将 m1[i.first + k] 置为0，表示积分为 i.first + k 的用户都已经找到了对手，他们不会被计入系统匹配不起来的用户数量。

当 m1[i.first] 小于 m1[i.first + k] 时，积分为 i.first 的用户数量不足以和所有积分为 i.first + k 的用户配对。在这种情况下，积分为 i.first 的所有用户都可以找到积分差距为 k 的对手，所以他们不是系统匹配不起来的用户。然而，积分为 i.first + k 的用户中，只有 m1[i.first] 个用户可以找到对手，剩下的 m1[i.first + k] - m1[i.first] 个用户找不到对手。因此，需要将 m1[i.first + k] 减去 m1[i.first]，得到的结果就是无法找到对手的用户数量。

最后，遍历 map m1 中的每一对键值对 i，将 i.second 加到答案 ans 中。输出 ans，即系统一场对局都匹配不起来的用户数量。

AC代码

#include <algorithm>
#include <bitset>
#include <cmath>
#include <iostream>
#include <map>
#define AUTHOR "HEX9CF"
using namespace std;
using ll = long long;

const int N = 1e5 + 7;
const int INF = 0x3f3f3f3f;
const ll MOD = 1e9 + 7;

int n, k;
bitset<N> valid;
map<int, int> m1;

int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);

	cin >> n >> k;
	for (int i = 1; i <= n; i++) {
		int t;
		cin >> t;
		m1[t]++;
		valid[t] = 1;
	}
	if (k == 0) {
		// 同分匹配
		cout << valid.count() << "\n";
		return 0;
	}
	for (const auto i : m1) {
		// cout << i.first << " " << i.second << endl;
		if (valid[i.first + k] && m1[i.first + k] > 0) {
			// 将积分差恰好是 K 的两名用户匹配在一起
			// cout << i.first + k << " " << m1[i.first + k] << endl;
			if (m1[i.first] < m1[i.first + k]) {
				m1[i.first + k] -= m1[i.first];
			} else {
				m1[i.first + k] = 0;
			}
		}
	}
	ll ans = 0;
	for (const auto i : m1) {
		ans += i.second;
	}
	cout << ans << endl;
	return 0;
}