小美的数组删除

import java.util.*;

// 注意类名必须为 Main, 不要有任何 package xxx 信息
public class Main {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        // 注意 hasNext 和 hasNextLine 的区别
        StringBuilder sb = new StringBuilder();
        int t = in.nextInt();
        for (int i = 0; i < t; i++) {
            int n = in.nextInt();
            long k = in.nextInt();
            long x = in.nextInt();
            // System.out.println("n:"+n+", k:"+k+", x:"+x);
            HashSet<Integer> set = new HashSet<>();
            int[] as = new int[n];
            for (int j = 0; j < n; j++) {
                as[j] = in.nextInt();
            }
            long min = x * n;
            int cur = 0;
            for (int j = n - 1; j >= 0; j--) {
                set.add(as[j]);
                while (set.contains(cur)) {
                    cur++;
                }
                min = Math.min(x * j + k * cur, min);
                // System.out.println(set);
                // System.out.println("min:"+min+", cur:"+cur);
            }
            sb.append(min);
            sb.append("\n");
        }
        System.out.println(sb.toString());
    }
}

#include <iostream>
#include <vector>
#include <algorithm>
#include <numeric>
#include <unordered_map>
#include <unordered_set>
#include <set>
#include <stack>
#include <functional>
#include <math.h>
#include <queue>
#include <deque>
#include <map>
#include <thread>
#include <string.h>
#include <limits.h>
using namespace std;
using ll = long long;
using pii = pair<int,int>;
const int MOD = 1e9+7;
 
 
int main()
{
    int t;
    cin>>t;
    while(t--){
        int n;
        cin>>n;
        ll k,x;
        cin>>k>>x;
 
        vector<int> a(n);
        vector<int> cnt(n+1);
        for(int i=0;i<n;i++){
            cin>>a[i];
            cnt[a[i]]++;
        }
        int mex;
        for(int i=0;i<=n;i++){
            if(cnt[i]==0){
                mex = i;
                break;
            }
        }
        ll ans = k*mex;
        ll cur = 0;
        for(int i=0;i<n;i++){
            cur += x;
            cnt[a[i]]--;
            if(cnt[a[i]]==0){
                mex = min(mex,a[i]);
            }
            ans = min(ans,cur + k*mex);
        }
        cout<<ans<<endl;
    }
}

import java.util.*;

//字符串匹配问题 美团24秋招第一场笔试
public class Main {
    //第一题
    public String matchID(String s) {
        if (s.matches("^[a-zA-Z][0-9]+$")) {
            return "standard";
        } else if (s.matches("^[0-9][a-zA-Z]+$")) {
            return "special";
        } else if (s.matches("^[a-zA-Z][a-zA-Z0-9]+$")) {
            return "mix";
        } else {
            return "invalid";
        }
    }

    //第三题
    long[] mexAns;
    public long deletePayment(long[] nums, long k, long x) {
        int n = nums.length;
        if (n == 0) return 0;
        mexAns=null;
        long ans = Long.MAX_VALUE;
        long payment = Math.min(k * mex(nums, 0), (long) n * x);
        if (payment == 0) return 0;
        for (int i = 1; i < n; i++) {
            ans = Math.min(ans, payment);
            payment = (long) i * x + k * mex(nums, i);
        }

        return ans;
    }


    //mex函数测试通过
    public long mex(long[] nums, int i) {
        if(mexAns == null) {
            mexAns = mexList(nums);
        }
        return mexAns[i];
    }

    public long[] mexList(long[] nums) {
        int n = nums.length;
        if (n == 0) return new long[0];
        Set<Long> set = new HashSet<>();

        long[] dp = new long[n];
        dp[n - 1] = nums[n - 1] == 0 ? 1 : 0;
        set.add(nums[n - 1]);
        for (int i = n - 2; i >= 0; i--) {
            if (dp[i + 1] < nums[i]) {
                dp[i] = dp[i + 1];
                set.add(nums[i]);
            } else {
                long mex = dp[i + 1];
                set.add(nums[i]);
                while (set.contains(mex)) {
                    mex++;
                }
                dp[i] = mex;
            }
        }
        return dp;
    }

    public static void main(String[] args) {
        Main obj = new Main();
        Scanner sc = new Scanner(System.in);
        String nstr = sc.nextLine();
        int n = Integer.parseInt(nstr);
        for (int i = 0; i < n; i++) {
            String str2 = sc.nextLine();
            String[] lenKX = str2.split(" ");
            int len = Integer.parseInt(lenKX[0]);
            long[] nums = new long[len];

            int k = Integer.parseInt(lenKX[1]);
            int x = Integer.parseInt(lenKX[2]);
            String numsStr = sc.nextLine();
            String[] numStr = numsStr.split(" ");

            for (int h = 0; h < len; h++) {
                nums[h] = Long.parseLong(numStr[h]);
            }
            System.out.println(obj.deletePayment(nums, k, x));
        }
//        long[] nums = {4, 5, 2, 3, 1, 0};
//        int k = 3;
//        int x = 3;
//        System.out.println(obj.mex(nums, 0));
//        System.out.println(obj.deletePayment(nums, 3, 3));
    }
}

#include <iostream>
#include <vector>
#include <unordered_set>
#include <algorithm>
using namespace std;

int main() {
    int t;cin>>t;
    while(t--){
        int n;
        long long k,x;
        cin>>n>>k>>x;
        vector<int> a(n);
        unordered_set<int> u_set;

        for(int i=0;i<=n;++i) u_set.insert(i);

        for(int i=0;i<n;++i){
            cin>>a[i];
            if(u_set.find(a[i])!=u_set.end()) u_set.erase(a[i]);
        }

        vector<int> tmp(u_set.begin(),u_set.end());
        sort(tmp.begin(),tmp.end());
        int mex=tmp[0];

        long long res=k*(long long)(mex);
        for(int i=0;i<n;++i){
            mex=min(mex,a[i]);
            res=min(res,(long long)(i+1)*x+k*(long long)(mex));
        }
        cout<<res<<endl;
    }
    return 0;
}
// 64 位输出请用 printf("%lld")

刚开始写很容易越界，得不断debug

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.List;
import java.util.stream.Collectors;
public class Main {
    int k, x;
    List arr;
    int[] counts;
    public static void main(String[] args) {
        Main m = new Main();
        m.task();
    }
    public void task() {
        try (BufferedReader br = new BufferedReader(new InputStreamReader(System.in))) {
            int T = Integer.parseInt(br.readLine());
            for (int i = 0; i < T; ++i) {
                List first = Arrays.stream(br.readLine().split(" "))
                                      .map(Integer::parseInt)
                                      .collect(Collectors.toList());
                k = first.get(1);
                x = first.get(2);
                arr = Arrays.stream(br.readLine().split(" "))
                      .map(Integer::parseInt)
                      .collect(Collectors.toList());
                counts = new int[first.get(0) + 1];
                for (int num : arr) {
                    ++counts[num];
                }
                int MEX = counts.length; // 默认都存在
                for (int j = 0; j < counts.length; ++j) {
                    if (counts[j] == 0) {
                        MEX = j;
                        break;
                    }
                }
                System.out.println(minCost(0, MEX));
            }
        } catch (IOException e) {
        }
    }
    //递归
    private long minCost(int i, int MEX) {
        if (i == arr.size()) {
            return 0;
        }
        int nextMEX = MEX;
        int elem = arr.get(i);
        if ((--counts[elem] == 0) && (elem < MEX)) {
            nextMEX = elem;
        }
        return Math.min((long)k * MEX, x + minCost(i + 1, nextMEX));
    }
}