知名网站建设,傻瓜网页制作工具,洛可可设计公司logo,百度站内搜索 wordpress[蓝桥杯 2017 国 B] 对局匹配
题目描述
小明喜欢在一个围棋网站上找别人在线对弈。这个网站上所有注册用户都有一个积分#xff0c;代表他的围棋水平。
小明发现网站的自动对局系统在匹配对手时#xff0c;只会将积分差恰好是 K K K 的两名用户匹配在一起。如果两人分差小…[蓝桥杯 2017 国 B] 对局匹配
题目描述
小明喜欢在一个围棋网站上找别人在线对弈。这个网站上所有注册用户都有一个积分代表他的围棋水平。
小明发现网站的自动对局系统在匹配对手时只会将积分差恰好是 K K K 的两名用户匹配在一起。如果两人分差小于或大于 K K K系统都不会将他们匹配。
现在小明知道这个网站总共有 N N N 名用户以及他们的积分分别是 A 1 , A 2 , ⋯ A N A_1,A_2, \cdots A_N A1,A2,⋯AN。
小明想了解最多可能有多少名用户同时在线寻找对手但是系统却一场对局都匹配不起来任意两名用户积分差不等于 K K K
输入格式
第一行包含两个个整数 N N N 和 K K K。
第二行包含 N N N 个整数 A 1 , A 2 , ⋯ , A N A_1,A_2, \cdots, A_N A1,A2,⋯,AN。
输出格式
一个整数代表答案。
样例 #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 % 30\% 30% 的数据 1 ≤ N ≤ 10 1 \le N \le 10 1≤N≤10。
对于 100 % 100\% 100% 的数据 1 ≤ N ≤ 1 0 5 1 \le N\le 10^5 1≤N≤105 0 ≤ K , A i ≤ 1 0 5 0\le K,A_i \le 10^5 0≤K,Ai≤105 。
时限 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;
bitsetN valid;
mapint, 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;
}
