[NERC2018] Lazyland

佬头 · 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