题解 CF727F 【Polycarp's problems】

· · 题解

提供一篇贪心的题解。

题意转化：

  每次给定a[0],求要删去几个数使得a的任意位置前缀和不为负数。

Solution：

  首先我们考虑前缀和的本质，就是一个个正数努力去抵消负数的过程，并且一个整数只能抵消下标在自己之后的负数。

  我们再次思考，每个正数会去抵消哪些负数，它一定会先消绝对值较小的，因为最后我们不管手动删去负的多的还是负的少的，代价都是1。

  那么我们只要从后往前扫一遍，用堆来使得每个正数按最优策略消去尽量多的负数，剩下的就是要留给a[0]来消去的。

  然后我们对没消完的负数做个前缀和，每次二分查找a[0]能把剩下的抵消到哪里，剩下还是不能消去的就是我们要花代价手动消去的。

  这样复杂度就是O(nlogn+mlogn)

  当时写的时候没看见n<=750，就当成n<=1e5来做了。

Code：

#include<bits/stdc++.h>
using namespace std;
#define ll long long 
#define gc getchar()
inline ll read(){
    register ll x(0),f(1);register char c(gc);
    while(c>'9'||c<'0')f=c=='-'?-1:1,c=gc;
    while(c>='0'&&c<='9')x=x*10+c-48,c=gc;
    return f*x;
}
priority_queue<ll>q;
const int N=210000;
ll a[N],n,m,pre[N],cnt;
int main(){
    n=read();m=read();
    register int i;
    for(i=1;i<=n;i++)a[i]=read();
    for(i=n;i>=1;i--){
        if(a[i]<0){
            q.push(a[i]);
        }
        else{
            while(!q.empty()&&a[i]>=0){
                a[i]+=q.top();q.pop();
            }
            if(a[i]<0)q.push(a[i]);
        }
    }
    while(!q.empty()){
        pre[++cnt]=q.top();q.pop();
    }
    for(i=1;i<=cnt;i++)pre[i]=-pre[i]+pre[i-1];
    while(m--){
        ll x=read();
        cout<<(cnt-(upper_bound(pre+1,pre+1+cnt,x)-pre)+1)<<'\n';
    }
}