AtCoder Beginner Contest 329 F

F - Colored Ball (atcoder.jp)(启发式合并)

问题陈述

有 \(N\) 个编号为 \(1, 2, \ldots, N\) 的盒子。最初，盒子 \(i\) 中有一个颜色为 \(C_i\) 的小球。

给你\(Q\)个查询，你要按顺序处理。

每个查询都由一对整数 \((a,b)\) 给出，并要求您执行以下操作：

• 将所有球从方格 \(a\) 移到方格 \(b\)，然后打印方格 \(b\) 中不同颜色球的数量。

这里，方格 \(a\) 和 \(b\) 可能是空的。

题解

起初使用哈希直接模拟,但是这样会\(T\)成大傻子

赛后和学长讨论了一下,发现这题\(T\)的原因出了\(N,Q\)拉满以外也可能是总是把盒子中小球多的往少的合并,所以我们可以采用启发式合并,即每次把少的放进多的里面,如果是要我们大的往小的放,那我们可以直接交换盒子

#include <bits/stdc++.h>
#define debug(a) cout<<#a<<"="<<a<<'\n';

using namespace std;
using namespace std::chrono;
using i64 = long long;

typedef pair<i64, i64> PII;

int main() {
	ios::sync_with_stdio(false);
	cin.tie(nullptr);

	int N, Q;
	cin >> N >> Q;

	vector<unordered_map<int, int>> box(N + 1);
	vector<int> C(N + 1);

	for (int i = 1; i <= N; i ++) {
		cin >> C[i];
		box[i][C[i]] ++;
	}

	auto move = [&](int a, int b) {
		if (box[a].size() < box[b].size()) {
			for (auto &[x, y] : box[a]) {
				box[b][x] += y;
			}
			box[a].clear();
		} else {
			for (auto &[x, y] : box[b])
				box[a][x] += y;
			box[b].swap(box[a]);
			box[a].clear();
		}
		cout << box[b].size() << endl;
	};

	while (Q--) {
		int a, b;
		cin >> a >> b;
		move(a, b);
	}

	return 0;
}