请教（美团8.10笔试）

请教一下美团删除数组开销的那题，不知道为什么如下写法只能通过30%用例。

题目

给定长度为 n 的数组 a，每次可对 a 采取如下操作之一：

1. 删除第一个元素 a1，数组的长度减一，该操作的花费为 x。
2. 直接删除整个数组，花费为 k*MEX(a)。 （其中 MEX(a) 表示 a 中未出现过的最小非负整数。如 [0,1,2,4] 的 MEX 为 3 ）。

求将数组 a 全部清空的最小花费。

输入

第一行输入一个整数 T，表示测试数据的组数。

接下来每组测试数据包含两行：

• 第一行包含三个正整数 n, k, x 分别表示数组的长度、清空整个数组的消耗系数、移除单个元素的消耗。
• 第二行包含 n 个整数，表示数组中的元素。

数据范围

• 1≤T≤1000
• 1≤n≤2×10^5
• 1≤k,x≤10^9
• 数组中所有 n 之和不超过 2×10^5

只能通过30%用例的题解：

思路很简答，从最后一个元素开始dp，dp过程中维护 mex。

#include <iostream>
#include <vector>
#include <string>
// #include <unordered_set>
#include <queue>
#include <algorithm>

using namespace std;

long long int solve(vector<int> array, int n, long long int k, long long int x);

int main() {
    int T;
    cin >> T;

    int n = 0;
    long long int k = 0, x = 0;

    for (int i = 0; i < T; i++)
    {
        cin >> n >> k >> x;

        vector<int> input;
        input.resize(n);

        for (int j = 0; j < n; j++)
        {
            cin >> input[j];
        }

        if (i != 0) cout << endl;

        printf("%lld", solve(input, n, k, x));
    }
}

long long int solve(vector<int> array, int n, long long int k, long long int x)
{
    vector<long long int> costs;
    costs.resize(n + 1);
    costs[0] = 0;

    int base = 0;
    priority_queue<int, vector<int>, greater<int> > q;
    
    for (int i = 1; i <= n; i++)
    {
        q.push(array[n - i]);

        while (q.top() == base)
        {
            base++;
            q.pop();
        }
        // new base got

        // cout << "i: "<< i << " ";
        // cout << "base: "<< base << endl;

        costs[i] = min(x + costs[i - 1], k * base);
    }

    return costs[n];
}

// 64 位输出请用 printf("%lld")

总不会是因为存 n 没用 long long 吧......