题解 P5653 【基础最优化练习题】
CYJian
·
·
题解
考虑在第 i 步选择的时候会对后缀都产生影响，所以不妨将 w_i 求后缀和。
令 S_i = \sum_{j=i}^{n} w_i，那么如果第 i 次 x 改变了 l_i，答案就是 \sum_{i=1}^{n}S_i \times l_i
考虑没有 a_i 的限制时，可以直接根据 S_i 是否大于 0 选择 +k 或者 -k
如果有了 a_i 的限制，那么就相当于限制了一个 l_i 的前缀和。
考虑到限制都是 \leq a_i 的形式，所以可以考虑每次削减前面选择 +k 的地方。
显然每次选择最小的 S_i 的位置削减是最优的。
那么拿一个堆维护 S_i 以及可以削减的次数 l_i 就好了。
```cpp
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int __SIZE = 1 << 18;
char ibuf[__SIZE], *iS, *iT;
#define ge (iS == iT ? (iT = (iS = ibuf) + fread(ibuf, 1, __SIZE, stdin), (iS == iT ? EOF : *iS++)) : *iS++)
#define ri read_int()
#define rl read_ll()
#define FILE(s) freopen(s".in", "r", stdin), freopen(s".out", "w", stdout)
template<typename T>
inline void read(T &x) {
char ch, t = 0; x = 0;
while(!isdigit(ch = ge)) t |= ch == '-';
while(isdigit(ch)) x = x * 10 + (ch ^ 48), ch = ge;
x = t ? -x : x;
}
inline int read_int() { int x; return read(x), x; }
inline ll read_ll() { ll x; return read(x), x; }
const int MAXN = 1000010;
ll w[MAXN];
int a[MAXN];
struct Node {
ll w;
int k;
Node() {}
Node(ll w, int k):w(w), k(k) {}
friend bool operator < (Node a, Node b) { return a.w < b.w; }
friend bool operator > (Node a, Node b) { return a.w > b.w; }
};
priority_queue<Node, vector<Node>, greater<Node> >q;
int main() {
#ifndef ONLINE_JUDGE
FILE("d");
#endif
int n = ri, k = ri;
for(int i = 1; i <= n; i++) a[i] = ri;
for(int i = 1; i <= n; i++) w[i] = ri;
for(int i = n; i >= 1; i--) w[i] += w[i + 1];
int x = 0; ll res = 0;
for(int i = 1; i <= n; i++) {
if(w[i] > 0) res += k * w[i], q.push(Node(w[i], k << 1)), x += k;
else res -= k * w[i], x -= k;
int c = x - a[i]; x = min(x, a[i]);
while(c > 0 && !q.empty()) {
Node x = q.top(); q.pop();
int t = min(c, x.k);
res -= t * x.w;
c -= t, x.k -= t;
if(x.k) q.push(x);
}
} cout << res << endl;
return 0;
}
```