题解 | #可口蛋糕#
可口蛋糕
https://ac.nowcoder.com/acm/problem/266839
在满足饱腹值大于等于M时，可口值越大越好。
因为饱腹值是正整数，只要找到一个区间[l,r]使得饱腹值之和大于等于M，那么[l,r+1]、[l,r+2]...[l,n]区间饱腹值之和也大于等于M。
现在问题变成两个：
1、如何找到小区间[l,r]使得饱腹值之和刚好大于等于M。
2、如何比较[l,r]、[l,r+1]、[l,r+2]...[l,n]这些区间可口值之和。
对第1个问题，可以使用滑动窗口来完成。从[0,0]区间开始，如何区间内饱腹值之和小于M就让r+1，否则处理第2个问题并让l+1。时间是O(n)的。
对于第2个问题，可以在第1个问题求解[l,r]饱腹值的时候同时记录[l,r]的可口值。这个问题就转换成了，从r+1开始的连续区间能得到可口度的最大值。直接计算时间是O(n)的，可以先预处理，每次进行查找时间O(1)。
从后往前，经过一趟计算，就可以计算出从某点开始连续的区间和的最大值。
#include <bits/stdc++.h>
using namespace std;
long long n,ans,sw,sm,W,w[1000001],d[1000001],sd[1000001];
int main(){
scanf("%lld%lld",&n,&W);
for(int i=0;i<n;i++)
scanf("%lld",&w[i]);
for(int i=0;i<n;++i)
scanf("%lld",&d[i]);
for(int i=n-1;i>=0;i--)
sd[i] = max(0ll,sd[i+1]+d[i]);//预处理从i开始连续区间能得到的最大可口度
int s=0;
ans = -1e16;
for(int t=0;t<n;++t){//遍历右端点
sw += w[t];
sm += d[t];
while(sw >= W){
ans = max(ans,sm+sd[t+1]);
sw -= w[s];
sm -= d[s];
++s;//左边去掉一个数再试试
}
}
printf("%lld\n",ans);
return 0;
}
投递谷歌等公司10个岗位 >
