#include <bits/stdc++.h>
using namespace std;

#define int long long

void solve() {
    int n;
    cin >> n;
    vector<int> a(n), b(n);
    for (auto &i: a) cin >> i;
    for (auto &i: b) cin >> i;
    
    // solve
    vector<int> pb(n+1);
    for (int i = 0; i < n; i++) pb[i+1] = pb[i]+b[i];
    vector<int> p(n+1);
    for (int i = 0; i < n; i++) p[i+1] = max(p[i], a[i]-pb[i]);
    vector<int> s(n+1);
    for (int i = n-1; i >= 0; i--) s[i] = max(s[i+1]-b[i],a[i]);

    int ans = 1e18;
    for (int i = 0; i < n; i++) {
        ans = min(ans, max(s[i],p[i]-pb[n]+pb[i]));
    }
    cout << ans << '\n';
}

signed main() {
    cin.tie(0)->sync_with_stdio(0);
    solve();
}

知识点

• 单调队列（P1886 滑动窗口 /【模板】单调队列）

• 前缀和

解题思路

暴力枚举

---

题目中要求选定一个 $j（1 \le j \le n）$，比太郎从 $j$ 开始按照

$$j,j+1,j+2,\cdots,n,1,2,\cdots,j-1$$

的顺序打怪。

我们很容易想到可以把这些怪看做一个环，比太郎打怪的过程相当于从环上一点按一定顺序遍历整个环，进而想到化环为链的思想。

定义

$$A_{i + n} = A_i,B_{i + n} = B_i(1 \le i < n)$$

。

假设第一次打的怪编号为 $j(1 \le j \le n)$，此时比太郎需要的初始力量的最小值为 $P_j$。

则

$$P_j=\max_{j \le i < n + j} ( A_i - \sum_{k = i}^{j - 1} B_k)$$

。

设比太郎需要的初始力量的最小值（即答案）为 $P$。

则

$$P=\min_{1 \le j \le n} P_j$$ $$P = \min_{1 \le j \le n} (\max_{j \le i < n + j} (A_i - \sum_{k = j}^{i - 1} B_k))$$

。

时间复杂度 $O(n^3)$，TLE 无疑。

考虑前缀和优化

---

观察这个求和

$$\sum_{k = j}^{i - 1} B_k$$

发现这部分计算可以用前缀和将时间复杂度优化成 $O(1)$。

定义前缀和数组

$$sum_i = \sum_{j = 1}^{i} B_j$$

则

$$\sum_{k = j}^{i - 1} B_k = sum_{i - 1} - sum_{j - 1}$$

则

$$P = \min_{1 \le j \le n} (\max_{j \le i < n + j} (A_i - (sum_{i - 1} - sum_{j - 1})))$$$$P = \min_{1 \le j \le n} (\max_{j \le i < n + j} (A_i - sum_{i - 1} + sum_{j - 1}))$$$$P = \min_{1 \le j \le n} (\max_{j \le i < n + j} (A_i - sum_{i - 1}) + sum_{j - 1})$$

。

为方便计算，设 $W_i=A_i - sum_{i - 1}$，则

$$P = \min_{1 \le j \le n} (\max_{j \le i < n + j} (W_i) + sum_{j - 1})$$

。

时间复杂度 $O(n^2)$，还是 TLE。

考虑使用单调队列

---

看出来了吗？这题就相当于在 $W$ 数组里寻找定长区间最大值，变成了一道模版题，可以参考模版题P1886。

时间复杂度降到 $O(n)$，顺利通过！

代码奉上

#include<bits/stdc++.h>
using namespace std;
//不开long long见祖宗 
#define ll long long
const ll MAXN=5e5+10,MAXLL=4611686018427387903;
ll n,a[2*MAXN],b[2*MAXN],sum[2*MAXN],w[2*MAXN],q[2*MAXN],ans=MAXLL;
int main() {
	scanf("%lld",&n);
	for(int i=1; i<=n; i++) {
		scanf("%lld",&a[i]);
		a[i+n]=a[i];
	}
	for(int i=1; i<=n; i++) {
		scanf("%lld",&b[i]);
		b[i+n]=b[i];
	}
	//前缀和 
	//计算sum[]、w[] 
	for(int i=1; i<=2*n-1; i++) {
		sum[i]=sum[i-1]+b[i];
		w[i]=a[i]-sum[i-1];
	}
	//使用单调队列 
	int head=1,tail=0;
	for(int i=1; i<=n-1; i++) {
		while(w[q[tail]]<=w[i]&&head<=tail) tail--;
		q[++tail]=i;
	}
	for(int i=n; i<=2*n-1; i++) {
		while(q[head]<i-n+1&&head<=tail) head++;
		while(w[q[tail]]<=w[i]&&head<=tail) tail--;
		q[++tail]=i;
		ans=min(ans,w[q[head]]+sum[i-n]);
	}
	printf("%lld",ans);
	return 0;
}