大神代码:
#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
int n,w;
const int N = 1e6+10;
LL f[N],d[N];
LL res = -2e18;
set<LL> s;
int main(){
cin>>n>>w;
for(int i=1;i<=n;i++){
cin>>f[i];
}
for(int i=1;i<=n;i++){
cin>>d[i];
d[i] +=d[i-1];//前缀和维护;
}
LL sum = 0;
for(int i=1,j = 1;i <= n;i++){
sum+=f[i];//取一段连续的区间;
//如果区间满足了饱腹度,吐出j的食物;
while(sum>w){
s.insert(d[j-1]);
sum -=f[j++];
}
if(!s.empty()) res = max(res,d[i] - *s.begin());
}
cout<<res<<endl;
return 0;
}
亮点 : 1.//如果区间满足了饱腹度,吐出j的食物;
while(sum>w){
s.insert(d[j-1]);//前j-1的可口度;
sum -=f[j++];
}
s中插入j-1而不是j,保证了在满足sum > w的条件下,吐出j-1的食物,失去前j-1的可口度;
2. if(!s.empty()) res = max(res,d[i] - *s.begin());
s已将前面j-1个食物的可口度前缀和按从小到大排序,无论选择(减去)哪个都满足连续且sum>w;
为了取到最大值,减去集合第一个数;
注意点:1.爆int也会超时
牛客官方代码
网址:
https://www.bilibili.com/video/BV1E5411v77a?p=5&vd_source=0457f83a57f1ab3400e4c1b0de9a0377
https://www.bilibili.com/video/BV1E5411v77a?p=5&vd_source=0457f83a57f1ab3400e4c1b0de9a0377
#include<bits/stdc++.h>
using namespace std;
int n,m;
typedef long long LL;
const int N = 1e6+10;
LL res = -2e18, sumw[N],w[N],sumd[N],d[N],mx[N];
int main(){
cin>>n>>m;
for(int i=1;i<=n;i++){
cin>>w[i]; sumw[i] = sumw[i-1] + w[i];
}
for(int i=1; i<= n;i++){
cin>>d[i]; sumd[i] = sumd[i-1] + d[i];
}
mx[n+1] = -2e18;
for(int i=n;i>=1;i--){
mx[i] = max(mx[i+1],sumd[i]);
}
for(int i=1;i<=n;i++){
int r = lower_bound(sumw+1,sumw+1+n,sumw[i-1]+m) - sumw;
res = max(res,mx[r]-sumd[i-1]);
}
cout<<res<<endl;
return 0;
}
新知识点:1.lower_bound的使用;
2.用后缀来维护最大值
mx[n+1] = -2e18;
for(int i=n;i>=1;i--){
mx[i] = max(mx[i+1],sumd[i]);
}
mx[i]表示从i~n 的最大值,即右边的最大值;