题解：P13512 [KOI 2025 #1] 稻草人

guoziyu_2023CSP · 2025-07-30 09:49:48 · 题解

很明显是贪心,每次选最大的几个数量最小。

思路：维护a数组的小根堆以及堆内元素的和。如果和小于P输出负一,否则尽可能删除最小的,减少所需数量。

代码：

#include<bits/stdc++.h>
using namespace std;
priority_queue<int,vector<int>,greater<> >q;//维护小根堆
int n,p,x,sum;//sum为q中的和
int main(){
    cin >> n >> p;
    for(int i = 1;i <= n;i++){
        cin >> x; sum += x;
        q.push(x); 
        if(sum < p) cout << "-1 ";//总和不够
        else{ while(sum - q.top() >= p){//能删就删，删最小的
                sum -= q.top(); q.pop();
            } cout << q.size() << " ";
        }
    } return 0;
}