自动搬运

查看原文

来自洛谷，原作者为

	佬头 {暴力出奇迹，骗分过样例，暴搜挂着机，打表出省一}ด้้้้้็้้้็็็็็้้้้้็็็็็้้้้้้็็็็็้้้้้็็็็็้้้้้้็็็็็้้้้้็็็็็้้้้้้็็็็็้้้้้็็็็็้้้้(已退役)

搬运于2025-08-24 22:51:57，当前版本为作者最后更新于2023-11-13 10:08:33，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

进了最优解第一，不得交发题解庆祝一下。

Description

现有 $n$ 个人和 $k$ 种职业，其中第 $i$ 个人正在从事职业 $a_i$。但是某些职业被空缺出来了，请你说服其中的某些人，使得每种职业都有人在做，对于第 $i$ 个人，你需要耗费 $b_i$ 的时间去说服。求出说服时间的最小值。

Solution

显然若职业 $j$ 正有 $w_j$ 个人在从事，我们肯定优先说服 $b$ 较小的人去从事其他职业，并且说服的人数不能多于 $w_j-1$。记这 $w_j$ 个人中 $b$ 最大的人的说服时间为 $maxx_j$，显然我们将 $w_j$ 个人全部说服去别的职业后仍然还要说服一个人回来，那么不如直接不动 $maxx_j$，考虑将剩下 $w_j-1$ 个人说服去空缺的职业。

若题目给定的 $a_i$ 有 $A$ 种，则显然我们只需要说服 $k-A$ 个人去从事空缺职业即可，并且我们有 $n-A$ 个人可以说服（不能说服的就是 $maxx_j$）。接下来思路就显得十分清晰了，我们只需要从这 $n-A$ 个人里面选出 $k-A$ 个 $b$ 最小的求个和就行了。

时间复杂度 $\mathcal O(n\log n)$。排序的 log 显然躲不掉。

Code

排序的方法有很多种，既然其他题解都是直接 sort()，那我就来一发优先队列 （带点小常数）。

#include <iostream>
#include <queue>
using namespace std;
const int N = 100005;
int n, k, a[N], b, maxx[N];
long long ans;
priority_queue <int, vector <int>, greater <int>> q;
int read(){
	int x = 0;
	char a = getchar();
	while(a < '0' || '9' < a) a = getchar();
	while('0' <= a && a <= '9') x = (x << 1) + (x << 3) + (a ^ 48), a = getchar();
	return x;
}
void write(long long x){
	if(x > 9) write(x / 10);
	putchar(x % 10 | 48);
}
int main(){
	n = read(), k = read();
	for(int i = 1; i <= n; ++ i) a[i] = read();
	for(int i = 1; i <= n; ++ i){
		b = read();
		if(!maxx[a[i]]) maxx[a[i]] = b, k --;
		else if(maxx[a[i]] < b) q.push(maxx[a[i]]), maxx[a[i]] = b;
		else q.push(b);
	}
	while(k --) ans += q.top(), q.pop();
	write(ans);
	return 0;
}

Similar

CF1089L Lazyland