526互联

Codeforces Round 773 (Div. 2) B. Power Walking

发布时间 2023-09-15 18:34:36作者: zsxuan

有 \(n\) 个增幅道具，第 \(i\) 个道具种类为 \(a_i\) ，一个人的强度 \(w\) 为他所有道具的种类数。对于 \(k ] \in[1, n]\) ，询问将 \(n\) 个道具分配给 \(k\) 个人且每个人至少分配到一个道具后，能够得到的最想强度和 \(\sum_{i=1}^{n} w_i\) 。

观察一：最低强度和 \(\sum_{i=1}^{k} w_i\) 最低即道具种类数 \(cnt\) 。

观察二：\(k \leq cnt\) 时，每种道具可以完全分配给一个人。\(\sum_{i=1}^{k} w_i = cnt\)

观察三：\(k > cnt\) 时，人数每比 \(cnt\) 多 \(1\) ，需要从一种中多分出一个道具，强度之和增加 \(1\) 。\(\sum_{i=1}^{k} w_i = cnt + (k - cnt) = k\) 。

view 
#include <bits/stdc++.h>
#define REP(i, A, N) for (int i = (int)A; i <= (int)N; i++)
#define PER(i, N, A) for (int i = (int)N; i >= (int)A; --i)
typedef long long ll;
void solve() {
	int n; std::cin >> n;
	std::set<int> px;
	REP(i,1,n) {int x;std::cin>>x;px.insert(x);}
	int m = px.size();
	REP(i,1,n) {
		std::cout << (i <= m ? m : i) << " \n"[i==n];
	}
}
int main() {
	int _ = 1; std::cin >> _;
	while ( _-- ) { solve(); }
	return 0;
}