CF1974G 题解

__vector__ · 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;
}