活动分组 码蹄集
题目来源:码蹄集
题目描述:
B站老师思路讲解链接:https://www.bilibili.com/video/BV1MX4y1R77W/?t=316.8&vd_source=3ae2a916df1bc5c1114c2bf3e95a2118
题目思路:
首先观察题目可得:每个人的能力值(A 和 B)是配对关系,即一个人既有 A 项目的能力值又有 B 项目的能力值。因此我们可以将每个人的 A 和 B 项目的能力值打包成一个元组 (a[i], b[i])。
接下来,我们需要找到一种合理的分组方案,使得每一组的两个人 A 能力值之和等于 B 能力值之和。由于本题中的数据规模最多为 1 0 5 10^5 105,暴力枚举所有的分组方案的时间复杂度为 O ( n 2 ) O(n^2) O(n2),无法通过本题。
因此考虑用贪心算法求解。我们将所有人按照 A 和 B 项目的能力值之和从小到大排序,然后依次分成若干组,使得每一组的两个人 A 能力值之和等于 B 能力值之和。具体过程为:
- 将所有人按照 A 和 B 项目的能力值之和从小到大排序;
- 依次取出第 1、2 名,第 3、4 名,第 5、6 名,…… 这些人,将他们配对,判断每组中的两个人的 A 能力值之和是否等于 B 能力值之和;
- 如果所有组都满足上述条件,则输出 YES;否则输出 NO。
这是一个贪心思路,因为我们首先要确保某一组中两个人 A 能力值之和等于 B 能力值之和,然后才去考虑整个团队的搭配问题。
Python代码实现:
import sys
from collections import defaultdict
n = int(input())
a_list = list(map(int, input().split()))
b_list = list(map(int, input().split()))
# 将每个人的 A 和 B 项目的能力值打包成一个元组 (a[i], b[i])
p = []
suma = sumb = 0
for i in range(n):
a = a_list[i]
suma += a
p.append((a, 0))
for i in range(n):
b = b_list[i]
sumb += b
p[i] = (p[i][0], b)
# 如果所有人的 A 和 B 项目的能力值之和不能够平均分配给每一组,则无法满足条件
if suma % (n // 2) != 0 or sumb % (n // 2) != 0:
print("NO")
sys.exit()
# 计算每组中 A 和 B 项目的能力值之和应该为多少
suma //= n // 2
sumb //= n // 2
# 使用字典记录每个元组出现的次数
s = defaultdict(int)
for x in p:
s[x] += 1
# 遍历元组列表,依次取出第 1、2 名,第 3、4 名,第 5、6 名,…… 这些人,将他们配对,
# 判断每组中的两个人的 A 能力值之和是否等于 B 能力值之和
for x in p:
if s[x] == 0: # 如果 x 元组已经被配对完毕,则跳过
continue
s[x] -= 1
y = (suma - x[0], sumb - x[1])
if s[y] == 0: # 如果 y 元组无法与 x 元组配对,则无法满足条件
print("NO")
sys.exit()
s[y] -= 1
print("YES")
Java代码实现:
import java.io.*;
import java.util.*;
public class Main {
static class Pair {
int first;
int second;
Pair(int first, int second) {
this.first = first;
this.second = second;
}
@Override
public boolean equals(Object obj) {
if (obj instanceof Pair) {
Pair other = (Pair)obj;
return first == other.first && second == other.second;
}
return false;
}
@Override
public int hashCode() {
return Objects.hash(first, second);
}
}
public static void main(String[] args) {
Scanner scanner = new Scanner(System.in);
int n = scanner.nextInt();
Pair[] p = new Pair[n];
int suma = 0, sumb = 0;
for (int i = 0; i < n; ++i) {
int a = scanner.nextInt();
p[i] = new Pair(a, 0);
suma += a;
}
for (int i = 0; i < n; ++i) {
int b = scanner.nextInt();
p[i].second = b;
sumb += b;
}
if (suma % (n / 2) != 0 || sumb % (n / 2) != 0) {
System.out.println("NO");
return;
}
suma /= n / 2;
sumb /= n / 2;
Map<Pair, Integer> s = new HashMap<>();
for (Pair x : p) {
s.putIfAbsent(x, 0);
s.put(x, s.get(x) + 1);
}
for (Pair x : p) {
if (s.get(x) == 0) continue;
s.put(x, s.get(x) - 1);
Pair y = new Pair(suma - x.first, sumb - x.second);
if (!s.containsKey(y) || s.get(y) == 0) {
System.out.println("NO");
return;
}
s.put(y, s.get(y) - 1);
}
System.out.println("YES");
}
}
C++代码实现:
参考原文链接:https://blog.csdn.net/m0_54754302/article/details/128277693
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using pii = pair<int, int>;
pii p[100005];
multiset<pii> s;
int main() {
int n;
ll suma = 0, sumb = 0;
cin >> n;
int m = n / 2;
for (int i = 1; i <= n; ++i) {
cin >> p[i].first;
suma += p[i].first;
}
for (int i = 1; i <= n; ++i) {
cin >> p[i].second;
sumb += p[i].second;
}
if (suma % m != 0 || sumb % m != 0) {
cout << "NO" << endl;
return 0;
}
suma /= m, sumb /= m;
for (int i = 1; i <= n; ++i) {
s.insert(p[i]);
}
for (int i = 1; i <= n; ++i) {
if (s.empty()) break;
if (s.find(p[i]) == s.end())
continue;
auto it = s.find(p[i]);
s.erase(it);
pii q = {suma - p[i].first, sumb - p[i].second};
if (s.find(q) == s.end()) {
cout << "NO" << endl;
return 0;
}
it = s.find(q);
s.erase(it);
}
cout << "YES" << endl;
}