题目描述

难度分:$2000$

输入$T(\leq 10^4)$表示$T$组数据。所有数据的$n$之和$\leq 2 \times 10^5$。

每组数据输入$n(1 \leq n \leq 2 \times 10^5)$，$x(1 \leq x \leq 1000)$表示有$n$个月，每个月的月底你会得到$x$元钱。

然后输入长为$n$的数组$c(1 \leq c[i] \leq 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 \lt i$，$i$是当前遍历到的月份。设当前手里的钱为$moeny$，有如下的两种情况：

1. 如果月初的时候$money \geq c[i]$，那就直接买幸福，幸福值自增，钱减少$c[i]$。
2. 否则我们看看堆顶元素（如果堆不为空）是不是大于$c[i]$，如果是就把之前那次$c[j](j \lt i)$反悔掉，钱增加$c[j]$再减少$c[i]$，因为是一换一所以幸福值不变。

复杂度分析

时间复杂度

遍历$c$数组的时间复杂度为$O(n)$，而每个$i$可能会进行$O(log_2n)$的堆操作，堆中元素的个数可以达到$O(n)$级别，所以整体的时间复杂度为$O(nlog_2n)$。

空间复杂度

主要的空间消耗就是堆的空间，在最差情况下其中会存$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;
}