本文章由 WyOJ Shojo 从洛谷专栏拉取，原发布时间为 2024-05-21 18:54:16

因为二模没打这场比赛，结果 vp 无伤 AK 了，哈哈。

想法 1

考虑 dp。
但是，可以发现无论如何都无法设计状态，使得状态总数在一个可控的范围内，故抛弃 dp。

想法 2

考虑这个问题的一个解，该怎么优化，才能使其变得更优秀。

注意到，如果某天以 $d$ 的代价购买了一个单位，那么如果后面某天单价 $e \lt d$，但是由于这天购买所花费的钱，而导致那天无法购买，那么肯定是不优的。

所以做法：维护一个优先队列，记录目前的购买状态。

从 $1$ 到 $m$ 天遍历，如果第 $i$ 天可以用剩余的钱直接购买，那么算进答案并加入队列；否则，看第 $i$ 天是否能替代掉队列中的一个元素。

#include <bits\/stdc++.h>
using namespace std;
const int maxn=2e5+5;
typedef long long ll;
int m,x;
int c[maxn];
void solve(){
	scanf("%d%d",&m,&x);
	for(int i=1;i<=m;i++){
		scanf("%d",&c[i]);
	}
	priority_queue<int> q;
	int s=0;
	for(int i=1;i<=m;i++){
		if(s>=c[i]){
			s-=c[i];
			q.push(c[i]);
 
		}else{
			if(!q.empty()&&q.top()>c[i]){
				s+=q.top();
				q.pop();
				s-=c[i];
				q.push(c[i]);
 
			}
		}
		s+=x;
	}
	printf("%d\n",int(q.size()));
}
int main(){
	int _;
	scanf("%d",&_);
	while(_--){
		solve();
	}
	return 0;
}