请教一下美团删除数组开销的那题,不知道为什么如下写法只能通过30%用例。
题目
给定长度为 n 的数组 a,每次可对 a 采取如下操作之一:
- 删除第一个元素 a1,数组的长度减一,该操作的花费为 x。
- 直接删除整个数组,花费为 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 吧......
全部评论
(3) 回帖