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