A 倚天剑的愤怒
题目大意 : 选出一个子集使得这些的前缀和都不会小于询问的相反数
-
从前往后贪心不对,要从后往前考虑
-
一个正数只能对后面的负数有效,而为了选取更多的武器,所以要给后面的负数开个堆,选越大的可选的就越多
Code
Show Code
#include <queue>
#include <cstdio>
#include <algorithm>
using namespace std;
typedef long long ll;
const int N = 1e6 + 5;
ll read(ll x = 0, int f = 1, char c = getchar()) {
for (; c < '0' || c > '9'; c = getchar()) if (c == '-') f = -1;
for (; c >='0' && c <='9'; c = getchar()) x = x * 10 + c - '0';
return x * f;
}
int n, m, a[N], ans[N], cnt;
priority_queue<int> q;
ll b[N];
int main() {
n = read(); m = read();
for (int i = 1; i <= n; ++i)
a[i] = read();
for (int i = n; i >= 1; --i) {
int x = a[i];
if (x < 0) q.push(x);
else {
while (!q.empty() && x + q.top() >= 0) x += q.top(), q.pop();
if (!q.empty() && x) x += q.top(), q.pop(), q.push(x);
}
}
ans[cnt = 1] = q.size();
while (!q.empty()) ++cnt, b[cnt] = b[cnt-1] - q.top(), ans[cnt] = ans[cnt-1] - 1, q.pop();
b[++cnt] = 1e18;
while (m--) printf("%d
", ans[upper_bound(b + 1, b + cnt + 1, read()) - b - 1]);
return 0;
}
B 原谅 (Unaccepted)
题目大意 :
- 咕咕
Code
Show Code
C 收集 (Unaccepted)
题目大意 :
- 咕咕
Code
Show Code