首先想到应该是时间复杂度为O($n^2$)的暴力枚举。读入a[],b[]两个数组，然后依次枚举每个位，让b[i]的取值为0并且把b[i]中的数据存储下来，从1开始枚举得到w的自小值，最后的答案是a[0]减去w的最小值。

#include<iostream>
using namespace std;
const int N=1e5+10;
int a[N],b[N];
int main(){
    int n;cin>>n;
    for(int i=0;i<=n;i++){
        cin>>a[i];
    }
    for(int i=1;i<=n;i++){
        cin>>b[i];
    }
    for(int i=1;i<=n;i++){
        int x=b[i];b[i]=0;
        int w=0,ans=1e9;
        for(int j=1;j<=n;j++){
            w=w+b[j];
            w=w-a[j];
            ans=min(w,ans);
        }
        cout<<a[0]-ans<<" ";
        b[i]=x;
    }
    return 0;
}

暴力枚举只能过百分之八十的数据，接下来需要进行公式推导。w+$\sum_{i=1}^{n} b_{i-1}$>=$\sum_{i=1}^{n} a_i$，那w应该取 $\sum_{i=1}^{n} a_i$-$\sum_{i=1}^{n} b_{i-1}$的最大值，这里维护一个数组c[]来依次存储前面我们所说的差值。将b[i]的值赋为0并不影响前半部分的c[i]，但是后半部分的c[i]需要再加一个b[i]。所以在这里维护一个数组pre[]存储前i个数中c[i]的最值，再维护一个数组suf[]存储后i个数的最值。最后答案的取值就是max(pre[i],suf[i]+b[i])。

#include<iostream>//前缀和 
using namespace std;
const int N=1e5+10;
int a[N],b[N],ans[N];
int c[N],pre[N],suf[N];
int main(){
	int n;cin>>n;
	for(int i=1;i<=n+1;i++)cin>>a[i];
	for(int i=1;i<=n;i++)cin>>b[i];
	pre[0]=suf[n+2]=-1e9;
	for(int i=1;i<=n+1;i++){//需要自己进行公式推导 
		c[i]=c[i-1]+a[i]-b[i-1];//c[i]是对a[i]求和-b[i]的最大值 
		pre[i]=max(pre[i-1],c[i]);
	}
	for(int i=n+1;i;--i)suf[i]=max(suf[i+1],c[i]);//后缀的最大值 
	for(int i=1;i<=n;i++){
	ans[i]=max(pre[i],suf[i+1]+b[i]);//前缀不影响，后缀加上b[i]即可 
	cout<<max(ans[i],0)<<" ";	
	}
	return 0;
} 

前缀和->max前i-1个最大值，倒数(n-i+1)个最大值 1.设置1+n个结点acc(前缀和)，每个结点表示在此i结点上需要acc[i]才能到达下一节点，结点acc[0]为a[0],其余1~n的acc[i] = acc[i-1] + a[i] - b[i] 2.求得prefix[i](i属于0~n），prefix[0] =acc[0],其余prefix[i] = max(prefix[i-1] +,acc[i]),表示前i-1至少要满足的和通过结点i需要满足的能量，即为前i个，subfix同理 3.当结点i同学没睡，无法得到b[i]，此时对前i-1个结点无影响，对后面有，ans = max(prefix[i-1],sunfix[i]+b[i]),subfix为后面最大数，而因为从i处无法得到b[i]，则后面所有数包括subfix[i]，都要+b[i].

#include <iostream>
#include <vector>

using namespace std;

int main(){
    int n;
    cin>>n;
    vector<int> a(n+1);
    vector<int> b(n+1);
    for(int i= 0;i<=n;i++){
        cin>>a[i];
    }
    for(int i= 1;i<=n;i++){
        cin>>b[i];
    }
    vector<int> acc(n+1);
    vector<int> prefix(1+n);
    vector<int> subfix(1+n);

    acc[0] = a[0];
    prefix[0] = a[0];
    for(int i = 1;i <= n;i++){
        acc[i] = acc[i-1] + a[i] - b[i];
        prefix[i] = max(prefix[i-1],acc[i]);
    }
    subfix[n] = acc[n];
    for(int i = n-1;i>0;i--){
        subfix[i] = max(subfix[i+1],acc[i]);
    }
    int ans;
    for(int i = 1;i<=n;i++){
        ans = max(prefix[i-1],subfix[i]+b[i]);
        cout<<ans<<' ';
    }
}

$O(n^2)$ 和二分答案 $O(n\log V)$ 的做法不在这里讲，这里我们只讲利用前缀/后缀 $\min$ 性质的 $O(n)$ 做法。

我们设 $s_i$ 为“以 $0$ 号城市为起点”作为前提，从 $i$ 号城市能够成功出发，巡查所带来的能量总增量（可能为负）。则有：

• $s_0=-a_0$
• $s_i=s_{i-1}+(b_i-a_i)$

这个不解释，从 $i$ 出发会先获得 $b_i$ 的补给，再消耗 $a_i$ 的能量。

我们可以对 $s_i$ 分别做一次前缀 $\min$ 后缀 $\min$，对于以每一个城市为起点的计算，显然其过程中的最小能量总增量决定了答案，最小值的相反数即为答案。

从 $i$ 成功出发到 $n$ 成功出发的这一段，利用后缀 $\min$就可以求了，需要注意的是，此时不存在 $b_i$ 的补给，这段后缀 $\min$ 减去 $b_i$ 即可；而从 $0$ 号城市出发到 $i-1$ 号城市出发这一段，正常使用前缀 $\min$ 去求即可。

一个边界情况为：当全程的最小能量总增量均 $\ge 0$ 时，此时答案是 $0$。

#include <stdio.h>
#include <algorithm>
inline int rd()
{
    int k = 0, f = 1;
    char s = getchar();
    while (s < '0' || s > '9') f = (s == '-') ? 0 : f, s = getchar();
    while (s >= '0' && s <= '9') k = (k << 1) + (k << 3) + (s ^ '0'), s = getchar();
    return f ? k : -k;
}
inline void wr(int x)
{
    if (x < 0) putchar('-'), x = -x;
    if (x > 9) wr(x / 10);
    putchar((x % 10) ^ '0');
}
const int N = 100010;
int n;
int a[N], b[N];

int pre_s[N], suf_s[N];
int pre_mn[N], suf_mn[N];

int main()
{
    n = rd();
    for (int i = 0; i <= n; ++i) a[i] = rd();
    for (int i = 1; i <= n; ++i) b[i] = rd();

    pre_s[0] = pre_mn[0] = -a[0];
    for (int i = 1; i <= n; ++i) pre_s[i] = pre_s[i - 1] + (b[i] - a[i]), pre_mn[i] = std::min(pre_mn[i - 1], pre_s[i]);
    suf_mn[n] = pre_s[n];
    for (int i = n - 1; i >= 0; --i) suf_mn[i] = std::min(suf_mn[i + 1], pre_s[i]);

    for (int i = 1; i <= n; ++i, putchar(' '))
        wr(-std::min(std::min(pre_mn[i - 1], suf_mn[i] - b[i]), 0));
}