自动搬运

查看原文

来自洛谷，原作者为

	CYJian 今日はこっちの地方はどしゃぶりの晴天でした，昨日もずっと暇で一日満喫してました

搬运于2025-08-24 22:12:59，当前版本为作者最后更新于2019-11-13 19:56:06，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

考虑在第 $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$ 就好了。

$Code$ :

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