Luogu – P7287 -「EZEC-5」魔法

题意

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

  1. 花费 $a$ 魔法值,选择 $A$ 中的一个区间 $[l,r]$,将 $a_l, a_{l+1},\cdots, a_r$ 全部 $+1$.
  2. 花费 $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;
}
暂无评论

发送评论 编辑评论

|´・ω・)ノ
ヾ(≧∇≦*)ゝ
(☆ω☆)
(╯‵□′)╯︵┴─┴
 ̄﹃ ̄
(/ω\)
∠( ᐛ 」∠)_
(๑•̀ㅁ•́ฅ)
→_→
୧(๑•̀⌄•́๑)૭
٩(ˊᗜˋ*)و
(ノ°ο°)ノ
(´இ皿இ`)
⌇●﹏●⌇
(ฅ´ω`ฅ)
(╯°A°)╯︵○○○
φ( ̄∇ ̄o)
ヾ(´・ ・`。)ノ"
( ง ᵒ̌皿ᵒ̌)ง⁼³₌₃
(ó﹏ò。)
Σ(っ °Д °;)っ
( ,,´・ω・)ノ"(´っω・`。)
╮(╯▽╰)╭
o(*////▽////*)q
>﹏<
( ๑´•ω•) "(ㆆᴗㆆ)
😂
😀
😅
😊
🙂
🙃
😌
😍
😘
😜
😝
😏
😒
🙄
😳
😡
😔
😫
😱
😭
💩
👻
🙌
🖕
👍
👫
👬
👭
🌚
🌝
🙈
💊
😶
🙏
🍦
🍉
😣
Source: github.com/k4yt3x/flowerhd
颜文字
Emoji
小恐龙
花!
上一篇
下一篇