T6-盛宴 题解

题面

image
image

看到题,由于是求符合条件连续区间的某种值的特殊情况(本题中是最小),不难想到双指针。

对于区间中香味值之和(总香味值),可以直接从上一个区间推出。
对于刺激值的最大值(整体辣度),使用线段树/ST维护即可。

核心代码:

build(1,1,n);
int l=1,r=1;
int sf=f[1];
for(;l<=n;l++){
    while(sf<m&&r<n){
        r++;
        sf+=f[r];
    }
    if(sf>=m){
        ans=min(ans,query(1,l,r));
    }
    sf-=f[l];
}

666

哎,我太傻了竟然没想到双指针(