【洛谷-P7287】「EZEC-5」魔法 • TonyYin's Blog

题意#

给定数列 $a_1, a_2, \cdots, a_n$ ，可以对其进行下列操作。

花费 $a$ 魔法值，选择 $A$ 中的一个区间 $[l,r]$ ，将 $a_l, a_{l+1},\cdots, a_r$ 全部 $+1$ .
花费 $b$ 魔法值，选择 $A$ 中的一个区间 $[l,r]$ ，将 $a_l, a_{l+1},\cdots, a_r$ 全部 $\times 2$ .

现在可以做若干次操作，使得序列 $a$ 存在一个子区间，其元素之和不小于 $s$ .

求需要花费的最小魔法值。

$1\leq n\leq 10^5$ ， $1\leq a,b\leq 10^9$ ， $-10^9\leq a_i\leq 10^9$ ， $1\leq s\leq 10^9$ .

题解#

对于 $+1$ 操作，对整个序列都使用，一定不劣于只对序列的一段区间使用。

对于正数，直接 $\times 2$ 一定优于 $+1$ .

对于负数，需要先做若干次 $+1$ 到正数，之后再 $\times 2$ ，这样最优。

因此最终的操作序列一定先加后乘，形如：

+++\cdots++\times \times \times \cdots \times \times \times

由于 $1\leq s\leq 10^9$ ，若通过乘法操作能使区间和变大，则最多进行 $\log_2s$ 次乘法操作。

$\log_2 s < 30$ ，所以可以枚举乘法操作的次数。

对于加法操作的次数，可以二分解决。

二分，每次 $\rm{check}$ 时，先线性求出执行完操作之后的新序列 $b$ ，之后递推地求出最大子段和。

求最大子段和，只需设 $f_i$ 表示以 $i$ 结尾的最大子段和， $f_i=\max\{f_{i-1}+b_i, b_i\}$ ， $f$ 的最大值即为序列的最大子段和。

代码#

#include <bits/stdc++.h>
#define int __int128
using namespace std;
inline int read() {}
inline void out(int x) {}
const int MAXN = 1e5 + 10, inf = 0x3f3f3f3f3f3f3f3f;
int n, va, vb, s, a[MAXN], b[MAXN], ans = inf;
bool check(int add, int Pow) {
	for(int i = 1; i <= n; i++) b[i] = (a[i] + add) * Pow;
	int curf = 0, maxf = 0;
	for(int i = 1; i <= n; i++) {
		curf = max(curf + b[i], b[i]);
		maxf = max(maxf, curf);
	}
	return maxf >= s;
}
signed main() {
	n = read(), va = read(), vb = read(), s = read();
	for(int i = 1; i <= n; i++) a[i] = read();
	//外层枚举乘法次数
	for(int x = 0, Pow = 1; x <= 50; x++, Pow <<= 1ll) {
		int l = 0, r = 1e15, mid, mmin = inf;
		//内层二分加法次数
		while(l <= r) {
			mid = (l + r) >> 1ll;
			if(check(mid, Pow)) r = mid - 1, mmin = mid;
			else l = mid + 1;
		}
		if(mmin != inf)
			ans = min(ans, vb * x + va * mmin);
	}
	out(ans); putchar('\n');
	return 0;
}

cpp