题目描述
难度分:2000
输入T(≤104)表示T组数据。所有数据的n之和≤2×105。
每组数据输入n(1≤n≤2×105),x(1≤x≤1000)表示有n个月,每个月的月底你会得到x元钱。
然后输入长为n的数组c(1≤c[i]≤1000),表示你可以在第i月的月初支付c[i]元钱,可以得到1个单位的幸福。
注意第1月你没有钱,输出你能得到的幸福总量的最大值。
输入样例
6
3 3
2 2 2
6 5
2 2 8 2 6 8
6 4
4 10 3 8 6 10
2 1
1 1
4 1
4 1 3 1
4 2
1 3 4 3
输出样例
2
4
3
1
2
1
算法
反悔贪心
这个题比较简单,感觉难度远低于正常2000分的题目,比较容易发现是反悔贪心的做法。
用一个大根堆维护之前买幸福值的代价c[j],j<i,i是当前遍历到的月份。设当前手里的钱为moeny,有如下的两种情况:
- 如果月初的时候money≥c[i],那就直接买幸福,幸福值自增,钱减少c[i]。
- 否则我们看看堆顶元素(如果堆不为空)是不是大于c[i],如果是就把之前那次c[j](j<i)反悔掉,钱增加c[j]再减少c[i],因为是一换一所以幸福值不变。
复杂度分析
时间复杂度
遍历c数组的时间复杂度为O(n),而每个i可能会进行O(log2n)的堆操作,堆中元素的个数可以达到O(n)级别,所以整体的时间复杂度为O(nlog2n)。
空间复杂度
主要的空间消耗就是堆的空间,在最差情况下其中会存O(n)数量的元素,额外空间复杂度为O(n)。
C++ 代码
#include <bits/stdc++.h>
using namespace std;
const int N = 200010;
int T, n, x, c[N];
void solve() {
priority_queue<int> heap;
int money = 0, happiness = 0;
for(int i = 1; i <= n; i++) {
if(money < c[i]) {
if(!heap.empty()) {
if(heap.top() > c[i]) {
money += heap.top() - c[i];
heap.pop();
heap.push(c[i]);
}
}
}else {
money -= c[i];
happiness++;
heap.push(c[i]);
}
money += x;
}
printf("%d\n", happiness);
}
int main() {
scanf("%d", &T);
while(T--) {
scanf("%d%d", &n, &x);
for(int i = 1; i <= n; i++) {
scanf("%d", &c[i]);
}
solve();
}
return 0;
}