【梦境审查】前后缀的使用

如题可以知道，我们会随机更改某一个节点的值，同时我们需要计算在该路径全程的能量最低点（谷底）；我们又发现，该节点的值的改变，只会影响该节点往后的谷底（谷底需要减去b[i]），前驱节点的谷底不受影响，因此我们引入“前后缀”来解决该问题。
我们增加一个节点n+1来替代环路；
我们设置：

• prefix[i]为节点[0,i+1]之间的谷底，而subfix[i]为[i+1,n+1]之间的谷底；
• 同时为了计算前后缀，我们使用acc[i]来记录到达第i+1个节点的时候的总能量开销；\(acc[0]=a[0]\);\(acc[n]=\sum_{i=0}^{n}a[i]+\sum_{i=1}^{n}b[i]\)
• prefix[i] = max(prefix[i-1],acc[i]);subfix[i]=max(subfix[i+1],acc[i]);
• 因此最终的结果为如果第i个节点出事，w[i]=max(prefix(i-1),subfix(i)+b[i])；\(i\in[1,n]\)
  根据这个写出代码；

#include<iostream>
#include<cmath>
#include<vector>
using namespace std;int main(){int n;vector<int> a;//0-nvector<int> b;//0-n,b[i]=0；vector<int> w;//vector<int> cost_earn;cin >> n;for(int i = 0;i<=n;i++){int temp;cin >> temp;a.push_back(temp);}for(int i = 0;i <= n;i++){int temp;if(i == 0){temp=0;}else{cin >> temp;}b.push_back(temp);}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]);}for(int i = 1;i <=n;i++){w.push_back(max(prefix[i-1],subfix[i]+b[i]));}for(auto iter = w.begin();iter != w.end();iter++){cout << *iter << " ";}cout<<endl;
}

暴力解法：
二分查找，从0找到\(\sum_{i=0}^{n}a[i]\);

#include<iostream>
#include<cmath>
#include<vector>
using namespace std;
vector<int> a;//0-n
vector<int> b;//0-n
bool canReach(int energy,int j,int n){for(int i = 0;i <= n;i++){if(i == 0){energy -= a[i];if(energy < 0){return false;}}else if(i == j){energy -= a[i];if(energy < 0){return false;}}else{energy -= a[i];energy += b[i];if(energy < 0){return false;}}}return true;
}int main(){int n;cin >> n;int max_cost = 0;for(int i = 0;i<=n;i++){int temp;cin >> temp;a.push_back(temp);max_cost+=temp;}for(int i = 0;i <= n;i++){int temp;if(i == 0){temp=0;}else{cin >> temp;}b.push_back(temp);}for(int i = 1;i <=n;i++){int L = a[0];int R = max_cost;int mid = (L+R)/2;while(L < R){bool judge = canReach(mid,i,n);if(judge){//mid够了，放大范围R = mid;mid = (L+R)/2;continue;}else if(!judge){//mid不够，需要缩小范围L = mid + 1;mid = (L+R)/2;continue;}}if(canReach(L,i,n)){cout << L <<" ";}else if(canReach(R,i,n)){cout << R<<" ";}}cout<<endl;
}

二分思想：
浮点：

mid = (L+R)*0.5;
if check(mid):
R = mid;
else:
L = mid;

终止：while(abs(R-L)>eps);
可行解：mid
整数：

mid = (L+R)/2;
if check(mid):
R = mid;
else:
L = mid+1;

终止：while(L < R)
可行解：mid