自动搬运

查看原文

来自洛谷，原作者为

	Licykoc 红雨漂泊泛起了回忆怎么潜

搬运于2025-08-24 22:28:25，当前版本为作者最后更新于2021-01-26 19:26:50，作者可能在搬运后再次修改，您可在原文处查看最新版

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

以下是正文

题意：

给定一个长度为 $n$ 的数列，每次可以选择一段区间 $\times2$ 或 $+1$ ，不同操作有不同的代价。问在有一段连续子区间和 $>\ S$ 的情况下，最小代价为多少。

$\mathcal{Sol:}$

蒟蒻一开始看到题目毫无思路，便开始看数据范围。

发现 $1 \le n \le 10^5$ ！这不妥妥的 $\mathcal{O(n\ log\ n)}$ 算法嘛。稍微一想便可以明确主要算法为二分。

好了回归正题：既然要使用二分，那么该问题的单调性是什么呢？

魔法1 ：如果使用 $n$ 次可以满足要求，那么 $n+1$ 次的魔法也一定满足要求 。

魔法2 ：如果使用 $n$ 次可以满足要求，那么 $n+1$ 次的魔法也一定满足要求 。

好了，单调性找到了。似乎两个魔法都可以二分，但是 魔法1 的最大操作次数是 $S\ (1 \le S \le 10^9)$ ，如果枚举该魔法肯定凉凉。所以考虑枚举 魔法2 ，该魔法最大操作次数约为 $\mathcal{log (S)}$ ，效率还是很可观的。

那么既然确定了二分的魔法是魔法1，那我们就来思考二分怎么写，首先二分的模版如下（笔者习惯的打法）：

bool check (int now) {
	//something
}
int l = 0, r = MAX;
while (l <= r) {
	int mid = l + (r - l) / 2;
   if ( check(mid) ) r = mid - 1; 
   		else l = mid + 1;
}

这个 check 函数是用来判断 魔法1 使用次数为 $now$ ，在枚举的 魔法2 使用次数下，能否满足有一个子序列和 $>\ S$ 。

这里需要用到一个贪心的思想：因为 魔法2 使用的是乘法，对一个负数使用的话会使和更小，所以我们只对和为正数的子序列使用魔法。这就类似于求最大子段和的方法，若您想更对的地了解关于最大子段和的求法，可以参考这道题的题解，这里不再赘述，直接给出代码。

bool check (int now) {
	int t = 0, ans = (-1) * 1ll << 62;
	for (int i = 1 ; i <= n ; ++ i) {
		if (t < 0) t = 0;
		t += a[i] + x;
		ans = max(ans, t);
	}
	return ans >= ceil(S * 1.0 / (1ll << k));
    //这里的k就是枚举的魔法2次数，用除法是为了防爆long long
}

综上，我们得到了一个复杂度为 $\mathcal{O}(n\times log(S)\times 63)$ 的算法。

$Code:$

#include <bits/stdc++.h>
#define int long long
using namespace std;
template<typename T>
void read (T& x) {
	char c=getchar(); int w=0; x=0;
	for (;!isdigit(c);c=getchar()) w^=!(c^45);
	for (;isdigit(c);c=getchar()) x=(x*10)+(c^48);
	x=w?-x:x;
}
const int MAXN=2e5+10;
typedef long long ll;
int n,k,A,B,S;
int l,r,mid;
ll ans=1ll<<62-1ll;
ll a[MAXN];
bool check (int x) {
	int t=0,ans=(-1)*1ll<<62;
	for (int i=1;i<=n;++i) {
		if (t<0) t=0;
		t+=a[i]+x;
		ans=max(ans,t);
	}
	return ans>=ceil(S*1.0/(1ll<<k));
}
signed main () {
	ans=ans*2ll;
	read(n),read(A),read(B),read(S);
	for (int i=1;i<=n;++i) read(a[i]);
	for (k=0;k<=32;++k) {
		l=0; r=1e18; //上界记得开大，不然会WA
		while (l<=r) {
			mid=l+(r-l)/2;
			if (check(mid)) r=mid-1; else l=mid+1;
		}
		ans=min(ans,(ll)A*l+B*k);
	}
	printf("%lld",ans);
}

Upd:

1.感谢SSerxhs提醒，修改sb错误。

2.感谢SSerxhs的hack，修改了部分代码。