自动搬运

查看原文

来自洛谷，原作者为

	MonKeySort_ZYczc 从来如此，便对么？||我太追求力量了，这让我时常感到自卑||代词使用“他”或“它”||8年级只有绿√的蒟蒻||不拿蓝√不改签||快读写错见祖宗

搬运于2025-08-24 23:09:15，当前版本为作者最后更新于2025-08-06 16:23:48，作者可能在搬运后再次修改，您可在原文处查看最新版

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

以下是正文

---

思路流程

直接处理很麻烦，先断环成链。
为习惯与下文叙述方便，假设断环成链后 $A_{i+n}=A_i(i<n)$，$B$ 数组同理。
把 $B_i$ 做前缀和，设前缀和数组为 $S_i$。
容易发现，假如第一个打的怪物是 $i(1\le i\le n)$，此时比太郎需要

$$\max_{i\le j<i+n}(A_j-(S_{j-1}-S_{i-1}))$$

的力量，将式子化为

$$\max_{i\le j<i+n}(A_j-S_{j-1}+S_{i-1})$$

再化为

$$\max_{i\le j<i+n}(A_j-S_{j-1})+S_{i-1}$$

发现，$A_j-S_{j-1}$ 是不随 $i$ 变化的，因此提前处理，让 $A_j:=A_j-S_{j-1}$。
此时问题转化为定长区间最大值问题，单调队列解决就行。
答案即为

$$\min_{1\le i\le n}(\max_{i\le j<i+n}(A_j-S_{j-1})+S_{i-1}) $$

。

总时间复杂度：$O(n)$。

哦对了，别忘开 long long 了。

代码实现

#include<bits/stdc++.h>
using namespace std;
#define int long long 
const int N=1e6+10;
int n,a[N],b[N],que[N<<2][2],head=1,tail,ans=0x3f3f3f3f3f3f3f3fll;
signed main(){
	ios::sync_with_stdio(0);
	cin.tie(0);cout.tie(0);
	cin>>n;
	for(int i=1;i<=n;i++) cin>>a[i],a[i+n]=a[i];
	for(int i=1;i<=n;i++) cin>>b[i],b[i+n]=b[i];
	for(int i=1;i<2*n;i++) a[i]-=b[i-1],b[i]+=b[i-1];
	for(int i=1;i<n;i++) 
	{
		while(head<=tail&&que[tail][1]<=a[i]) tail--;
		tail++;que[tail][0]=i;que[tail][1]=a[i];
	}
	for(int i=n;i<2*n;i++)
	{
		while(head<=tail&&que[head][0]<i-n+1) head++;
		while(head<=tail&&que[tail][1]<=a[i]) tail--;
		tail++;que[tail][0]=i;que[tail][1]=a[i];
		ans=min(ans,que[head][1]+b[i-n]);
		//cout<<que[head][1]+b[i-n]<<endl;
	}
	cout<<ans;
}