洛谷 P7023

首先可以发现一些有用的性质：

• 每个数至多操作一次
• 如果一个数，在原数列中有它的倍数，那么改变成那个数一定是最优的。否则可以改变成所有数的最小公倍数。

贪心的，按出现次数从小到大依次改。

对两种情况分别跑一次，取个 \(\min\)。

Code：

#include <bits/stdc++.h>
using namespace std;
const int N = 300005, M = 1000005;
int n, m, cnt;
int a[N], ans[N];
int vis[M];
vector <int> v1, v2;

int main() {
	scanf("%d", &n);
	for (int i = 1; i <= n; ++i) {
		scanf("%d", &a[i]);
		if (!vis[a[i]]) ++cnt; ++vis[a[i]];
	}
	sort(a + 1, a + n + 1), m = unique(a + 1, a + n + 1) - (a + 1);
	memset(ans, 0x3f, sizeof ans), ans[0] = cnt;
	for (int i = 1; i <= m; ++i) {
		v2.push_back(vis[a[i]]);
		for (int j = a[i] * 2; j <= 1000000; j += a[i]) {
			if (vis[j]) {
				v1.push_back(vis[a[i]]);
				break;
			}
		}
	}
	sort(v1.begin(), v1.end()), sort(v2.begin(), v2.end());
	int cur = 0;
	for (int i = 0; i < v1.size(); ++i) {
		cur += v1[i];
		ans[cur] = min(ans[cur], cnt - i - 1);
	}
	cur = 0;
	for (int i = 0; i < v2.size(); ++i) {
		cur += v2[i];
		ans[cur] = min(ans[cur], cnt - i);
	}
	printf("%d ", ans[0]);
	for (int i = 1; i <= n; ++i) printf("%d ", ans[i] = min(ans[i], ans[i - 1]));
	return 0;
}