题解：P10647 [NordicOI 2023] Ice Cream Machines

· · 题解

P10647 题解

前言

这道题和果汁店的难题很像，但数据大小差异巨大。同时果汁店的难题的机器如果以前没有使用过无需清洗直接可以使用，这道题则不行。

朴素做法

贪心即可

注意到客人的请求是有序的，即不能直接 sort。

很明显，若制作时已经有相同口味的机器，一定使用这台机器。

若没有相同口味的，看有无新机器，有则一定使用。若清洗已经用过的机器，可能这个机器将来还会用到，即使不会，用新机器也一定是最优解之一，因为后来没有新机器之后也能再清洗以后用不着的那个机器。

若没有新机器，看有无后来不用了的机器，有则一定清洗那个机器，因为后来不用因为这次清洗产生额外清洗量。

若以上条件均不满足，就进入到了整个题目最重要的一步。

一定清洗最晚有需求的那个。

证明：

定义少清洗量为无需清洗就能制作的冰淇淋数量。

根据条件（即前面的假设都不符合），若清洗最晚有需求的那个，则少清洗量至少为 k-1，因为既然清洗的是清洗最晚有需求的那个，那么其他机器在它有需求之前至少有一次需求。

若不选择它，则少清洗量一定小于清洗最晚有需求的那个的少清洗量，因为最晚有需求的那个再次之前，根据定义，不可能有需求，因此少清洗量就少了最晚有需求的那个在下次使用之前对新选择的另一个的需求量。

根据题目要求，少清洗量越大越好，因此我们的选择一定最优。

朴素代码

贴上朴素代码（79pts）：

#include <bits/stdc++.h>
using namespace std;
const int MAXN = 200005;
int m, k, n, ans = 0;
queue<int> pos[MAXN];
bool has[MAXN];
int mac[MAXN], use = 0;
int ice[MAXN], where;

void an_pai(int x) {
    pos[x].pop();
    if (!has[x]) {
        ans++;
        if (use < k) {
            mac[++use] = x;
            has[x] = true;
            return;
        }
        int far = 0, bes;
        for (int i = 1; i <= use; i++)
            if (pos[mac[i]].empty()) {
                has[mac[i]] = false;
                has[x] = true;
                mac[i] = x;
                return ;
            } else if (far < pos[mac[i]].front())
                far = pos[mac[i]].front(), bes = i;
        has[mac[bes]] = false;
        mac[bes] = x;
        has[x] = true;
    }
}

int main() {
    scanf("%d%d%d", &n, &m, &k);
    for (int i = 1, x; i <= n; i++) {
        scanf("%d", &x);
        pos[x].push(i);
        ice[i] = x;
    }
    for (where = 1; where <= n; where++)
        an_pai(ice[where]);
    printf("%d", ans);
    return 0;
}

优化

不难看出朴素解法的时间复杂度是 O(n)\sim O(nk) 的，T 了最后一个点。

我们对下一次需求的时间进行大顶堆维护即可。为方便，若没有下一次需求，将其设为极大值即可。

码

code（与朴素版本差别巨大）：

#include <bits/stdc++.h>
using namespace std;
const int MAXN = 200005;
priority_queue<pair<int, int> > h;
int a[MAXN], nex[MAXN], mac[MAXN], cnt, ans, n, m, k;
bool has[MAXN];

int main() {
    scanf("%d%d%d", &n, &m, &k);
    for (int i = 1; i <= n; i++) {
        nex[i] = n + 1;
        scanf("%d", a + i);
        nex[mac[a[i]]] = i;
        mac[a[i]] = i;
    }
    for (int i = 1; i <= n; i++) {
        if (has[a[i]]) {
            h.push(make_pair(nex[i], a[i]));
            continue;
        }
        if (cnt == k) {
            int bes = h.top().second;
            has[bes] = false;
            h.pop();
            cnt--;
        }
        h.push(make_pair(nex[i], a[i]));
        has[a[i]] = true;
        cnt++;
        ans++;
    }
    printf("%d", ans);
    return 0;
}