方法思路

为了找到将数组全部清空的最小代价，我们需要考虑两种操作：逐个删除元素和整体删除数组。具体步骤如下：

1. 计算后缀MEX值：对于数组的每一个可能的后缀（即从第i个元素到末尾的子数组），计算其MEX值。MEX是数组中未出现的最小非负整数。
2. 遍历所有可能的操作组合：假设我们删除前i个元素（逐个删除，花费ix），然后删除剩下的整个数组（花费kMEX(剩余数组)）。我们需要计算所有可能的i（从0到n）的总花费，并找出其中的最小值。

代码实现

Java

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

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int t = Integer.parseInt(br.readLine());
        
        StringBuilder sb = new StringBuilder();
        while (t-- > 0) {
            String[] line = br.readLine().split(" ");
            int n = Integer.parseInt(line[0]);
            long k = Long.parseLong(line[1]);
            long x = Long.parseLong(line[2]);
            
            line = br.readLine().split(" ");
            int[] arr = new int[n];
            for (int i = 0; i < n; i++) {
                arr[i] = Integer.parseInt(line[i]);
            }
            
            long minCost = solve(arr, n, k, x);
            sb.append(minCost).append("\n");
        }
        
        System.out.print(sb);
    }
    
    private static long solve(int[] arr, int n, long k, long x) {
        // 计算每个后缀的MEX值
        int[] mexSuffix = new int[n + 1];
        
        for (int i = n; i > 0; i--) {
            boolean[] exists = new boolean[n + 1];
            for (int j = i - 1; j < n; j++) {
                if (arr[j] <= n) {
                    exists[arr[j]] = true;
                }
            }
            
            int mex = 0;
            while (mex <= n && exists[mex]) {
                mex++;
            }
            mexSuffix[i - 1] = mex;
        }
        
        // 计算最小代价
        long minCost = Long.MAX_VALUE;
        long prefixCost = 0;
        
        for (int i = 0; i <= n; i++) {
            // i个元素单独删除的代价 + 剩余元素整体删除的代价
            long currentCost = prefixCost;
            if (i < n) {
                currentCost += k * mexSuffix[i];
            }
            
            minCost = Math.min(minCost, currentCost);
            
            if (i < n) {
                prefixCost += x;
            }
        }
        
        return minCost;
    }
}

Python

import sys

def solve():
    input = sys.stdin.read().split()
    ptr = 0
    t = int(input[ptr])
    ptr += 1
    results = []
    
    for _ in range(t):
        n = int(input[ptr])
        k = int(input[ptr + 1])
        x = int(input[ptr + 2])
        ptr += 3
        arr = list(map(int, input[ptr:ptr + n]))
        ptr += n
        
        # 计算整个数组的MEX
        mex_all = 0
        seen = set(arr)
        while mex_all in seen:
            mex_all += 1
        
        # 初始化最小代价
        min_cost = k * mex_all
        
        # 逐个删除元素并计算剩余部分的MEX
        current_cost = 0
        current_mex = mex_all
        freq = {}
        for num in arr:
            freq[num] = freq.get(num, 0) + 1
        
        for i in range(n):
            # 删除arr[i]，更新频率和current_mex
            num = arr[i]
            freq[num] -= 1
            if freq[num] == 0:
                del freq[num]
                if num < current_mex:
                    current_mex = num
            
            # 计算当前剩余部分的MEX
            while current_mex in freq:
                current_mex += 1
            
            # 更新最小代价
            current_cost += x
            total_cost = current_cost + k * current_mex
            if total_cost < min_cost:
                min_cost = total_cost
        
        results.append(min_cost)
    
    print('\n'.join(map(str, results)))

solve()

C++

#include <iostream>
#include <vector>
#include <climits>
using namespace std;

long long solve(const vector<int>& arr, int n, long long k, long long x) {
    // 计算每个后缀的MEX值
    vector<int> mexSuffix(n + 1);
    
    for (int i = n; i > 0; i--) {
        vector<bool> exists(n + 1, false);
        for (int j = i - 1; j < n; j++) {
            if (arr[j] <= n) {
                exists[arr[j]] = true;
            }
        }
        
        int mex = 0;
        while (mex <= n && exists[mex]) {
            mex++;
        }
        mexSuffix[i - 1] = mex;
    }
    
    // 计算最小代价
    long long minCost = LLONG_MAX;
    long long prefixCost = 0;
    
    for (int i = 0; i <= n; i++) {
        // i个元素单独删除的代价 + 剩余元素整体删除的代价
        long long currentCost = prefixCost;
        if (i < n) {
            currentCost += k * mexSuffix[i];
        }
        
        minCost = min(minCost, currentCost);
        
        if (i < n) {
            prefixCost += x;
        }
    }
    
    return minCost;
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    
    int t;
    cin >> t;
    
    while (t--) {
        int n;
        long long k, x;
        cin >> n >> k >> x;
        
        vector<int> arr(n);
        for (int i = 0; i < n; i++) {
            cin >> arr[i];
        }
        
        cout << solve(arr, n, k, x) << endl;
    }
    
    return 0;
}