CF727F Polycarp's problems 题解

题意：

有 \(n\) 道题目，每道题目有一个质量 \(a_i\) (可正可负)，题目按照一定顺序排列。cxy 作为出题人，由于不想让参赛者认为是毒瘤题，因此决定删减一些题目。

不妨设一个参赛者的初始心情为 \(q\)，他会按照顺序阅读这些题目。每读一道题目，他的心情会随着题目的质量改变。意思是说，如果他读了一道质量为 \(b\) 的题目，他的心情就会增加 \(b\) (即心情为 \(q, q+a_1, q+a_1+a_2, \cdots\))。

如果在读了某些题目后，参赛者的心情变为了负数，则他会立即停止阅读且认为这个题库是毒瘤题。

cxy 想知道，为了不让参赛者认为是毒瘤题 (即要使他们的心情时刻保持非负)，最少需要 (在题库中) 移除多少道题目 (其余题目的顺序保持不变)。由于 cxy 不知道参赛者的初始心情，但她有 \(m\) 次猜测 " 参赛者的初始心情 \(q = b_i\)"。

对于她的每次猜测，找到满足条件的移除题目数的最小值。

输入格式：

第一行包含两个正整数 \(n, m,~(n \leq 750, m \leq 2 \times 10^5)\)，表示题库中题目的数量和 cxy 猜测初始心情的次数。

第二行包含 \(n\) 个整数 \(a_1, a_2, \cdots, a_n,~(|a_i| \leq 10^9)\)，表示题目的质量。

第三行包含 \(m\) 个非负整数 \(b_1, b_2, \cdots, b_m,~(b_i \leq 10^{15})\)，表示 cxy 对参赛者的初始心情的猜测。

输出格式：

输出 \(m\) 行，每行一个整数 \(s_i\)，表示当 \(q = b_i\) 时删除题目的最小值。

~~嗨害嘿，又是我不会的贪心。。虽然我其实已经想出来一大半了~~

题目其实可以转化为：

多次询问，每次给定 \(a_0\) ，求至少删去几个数可以使所有 \(S_i \ge 0\)

其中 \(S_i\) 为前缀和，即 \(S_i = \sum_{j=1}^{i} a_j\)

考虑前缀和的本质，其实就是用正的 \(a_i\) 去消负的 \(a_i\)

容易想到，我们会尽可能抵消掉绝对值小的 \(a_i(a_i < 0)\)

为什么呢？因为我们删除一个负数，无论它绝对值多大，都花费 \(1\)

到目前为止都是简单的贪心。

那么多次询问怎么处理呢？

我们可以假设询问前 \(a_0\) 为 \(0\) ，然后找到所有消不掉的负数

然后把这些负数的绝对值做一个前缀和（注意要先按绝对值升序排序！）

因为它给的 \(a_0 \ge 0\) ，所以我们直接二分 \(a_0\) 能消掉几个，用消不掉的负数的数量减掉就好了

时间复杂度 \(O((n + q)\log n)\)

代码：

#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cstdarg>
#include <cmath>
#include <iomanip>
#include <random>
#include <queue>
using namespace std;
#define int long long
#define INF 0x3f3f3f3f3f3f3f3f
#define N ((int)(2e5+15))

int n,m,o,a[N],c[N];
priority_queue<int> q;
#define ub(arr,n,x) (upper_bound(arr+1,arr+1+n,x)-arr)
signed main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);
    // freopen("check.in","r",stdin);
    // freopen("check.out","w",stdout);
    cin >> n >> m;
    for(int i=1; i<=n; i++) cin >> a[i];
    for(int i=n; i; 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()) c[++o] = q.top(), q.pop();
    for(int i=1; i<=o; i++) c[i] = -c[i] + c[i-1];
    for(int x; m--; ) cin >> x, cout << o - ub(c,o,x) + 1 << '\n';
    return 0;
}