小美的数组删除

[题目链接](https://www.nowcoder.com/practice/51eb44145cf645f7a6a1d75161ad4601)

思路

题意分析

小美有一个长度为 $n$ 的数组，可以执行两种操作：

删除首元素：花费 $x$ ，删除当前数组的第一个元素。
删除整个数组：花费 $k \times \text{MEX}(a)$ ，一次性清空数组。

其中 $\text{MEX}(a)$ 表示数组 $a$ 中未出现过的最小非负整数。目标是以最小代价清空数组。

关键观察

最优策略一定是：先从前面连续删除若干个元素（可能是 $0$ 个），然后对剩余数组执行一次"删除整个数组"。

设我们先删除前 $i$ 个元素，则：

删除首元素的花费为 $i \times x$ 。
剩余数组 $a[i \ldots n-1]$ 的 $\text{MEX}$ 为 $m_i$ ，删除整个数组的花费为 $k \times m_i$ 。
总花费为 $i \times x + k \times m_i$ 。

我们需要枚举所有 $i \in [0, n]$ ，取最小值。

MEX 的维护

从前往后依次删除元素时， $\text{MEX}$ 值只会不增（因为移除元素只可能减少某个值的出现次数，从而使 $\text{MEX}$ 变小或不变）。

具体做法：

用计数数组 $\text{cnt}[v]$ 记录当前数组中每个值的出现次数。
维护当前 $\text{MEX}$ 。
当删除 $a[i]$ 后，若 $\text{cnt}[a[i]]$ 变为 $0$ 且 $a[i] < \text{MEX}$ ，则 $\text{MEX}$ 更新为 $a[i]$ 。

由于 $\text{MEX}$ 单调不增，每次更新只需常数时间。

代码

C++
Java
Python3
JavaScript

#include <bits/stdc++.h>
using namespace std;

int main(){
    int T;
    scanf("%d", &T);
    while(T--){
        long long n, k, x;
        scanf("%lld%lld%lld", &n, &k, &x);
        vector<int> a(n);
        for(int i = 0; i < n; i++) scanf("%d", &a[i]);

        vector<int> cnt(n + 2, 0);
        for(int i = 0; i < n; i++){
            if(a[i] <= n) cnt[a[i]]++;
        }

        int mex = 0;
        while(mex <= n && cnt[mex] > 0) mex++;

        long long ans = k * mex;

        for(int i = 0; i < n; i++){
            if(a[i] <= n){
                cnt[a[i]]--;
                if(a[i] < mex && cnt[a[i]] == 0){
                    mex = a[i];
                }
            }
            long long cost = (long long)(i + 1) * x + k * mex;
            ans = min(ans, cost);
        }

        printf("%lld\n", ans);
    }
    return 0;
}

import java.util.*;
import java.io.*;

public class Main {
    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int T = Integer.parseInt(br.readLine().trim());
        StringBuilder sb = new StringBuilder();
        while (T-- > 0) {
            StringTokenizer st = new StringTokenizer(br.readLine().trim());
            int n = Integer.parseInt(st.nextToken());
            long k = Long.parseLong(st.nextToken());
            long x = Long.parseLong(st.nextToken());
            int[] a = new int[n];
            st = new StringTokenizer(br.readLine().trim());
            for (int i = 0; i < n; i++) {
                a[i] = Integer.parseInt(st.nextToken());
            }

            int[] cnt = new int[n + 2];
            for (int i = 0; i < n; i++) {
                if (a[i] <= n) cnt[a[i]]++;
            }

            int mex = 0;
            while (mex <= n && cnt[mex] > 0) mex++;

            long ans = k * mex;

            for (int i = 0; i < n; i++) {
                if (a[i] <= n) {
                    cnt[a[i]]--;
                    if (a[i] < mex && cnt[a[i]] == 0) {
                        mex = a[i];
                    }
                }
                long cost = (long)(i + 1) * x + k * mex;
                ans = Math.min(ans, cost);
            }

            sb.append(ans).append('\n');
        }
        System.out.print(sb);
    }
}

import sys
input = sys.stdin.readline

T = int(input())
out = []
for _ in range(T):
    n, k, x = map(int, input().split())
    a = list(map(int, input().split()))

    cnt = [0] * (n + 2)
    for v in a:
        if v <= n:
            cnt[v] += 1

    mex = 0
    while mex <= n and cnt[mex] > 0:
        mex += 1

    ans = k * mex

    for i in range(n):
        if a[i] <= n:
            cnt[a[i]] -= 1
            if a[i] < mex and cnt[a[i]] == 0:
                mex = a[i]
        cost = (i + 1) * x + k * mex
        if cost < ans:
            ans = cost

    out.append(str(ans))

print('\n'.join(out))

const readline = require('readline');
const rl = readline.createInterface({ input: process.stdin });
const lines = [];
rl.on('line', line => lines.push(line.trim()));
rl.on('close', () => {
    let idx = 0;
    const T = parseInt(lines[idx++]);
    const res = [];
    for (let t = 0; t < T; t++) {
        const parts = lines[idx++].split(' ');
        const n = parseInt(parts[0]);
        const k = BigInt(parts[1]);
        const x = BigInt(parts[2]);
        const a = lines[idx++].split(' ').map(v => parseInt(v));

        const cnt = new Array(n + 2).fill(0);
        for (let i = 0; i < n; i++) {
            if (a[i] <= n) cnt[a[i]]++;
        }

        let mex = 0;
        while (mex <= n && cnt[mex] > 0) mex++;

        let ans = k * BigInt(mex);

        for (let i = 0; i < n; i++) {
            if (a[i] <= n) {
                cnt[a[i]]--;
                if (a[i] < mex && cnt[a[i]] === 0) {
                    mex = a[i];
                }
            }
            const cost = BigInt(i + 1) * x + k * BigInt(mex);
            if (cost < ans) ans = cost;
        }

        res.push(ans.toString());
    }
    console.log(res.join('\n'));
});

复杂度分析

时间复杂度： $O(n)$ 。初始 $\text{MEX}$ 计算为 $O(n)$ ，之后每次删除首元素并更新 $\text{MEX}$ 为 $O(1)$ （因为 $\text{MEX}$ 单调不增），总共遍历 $n$ 次。
空间复杂度： $O(n)$ ，用于计数数组。