洛谷p4085
题目链接
首先想怎么计算一个区间的风味和辣度；风味是区间内的风味总和，可以用前缀和处理；辣度是区间最大值，可以用ST表处理；
处理完ST表和前缀和之后考虑怎么求答案，可以考虑二分查找前缀和满足风味要求的最小值，然后列举后面的所有情况求最小；
代码：
#include<bits/stdc++.h>
#define int long long
#define endl "\n"
using namespace std;
struct gan{int f,s;
}g[100005];
int n,m,f[100005][20],sum[100005];
inline int read()
{int x=0,f=1;char ch=getchar();while (ch<'0'||ch>'9'){if (ch=='-') f=-1;ch=getchar();}while (ch>='0'&&ch<='9'){x=x*10+ch-48;ch=getchar();}return x*f;
}
int lmax(int l,int r){//求区间最大值r++;int j=63-__builtin_clzll(r-l);return max(f[l][j],f[r-(1<<j)][j]);
}
signed main(){int ans=0x3f3f3f3f;n=read();m=read();int h=63-__builtin_clzll(n);for(int i=1;i<=n;i++){g[i].f=read();g[i].s=read();}for(int i=1;i<=n;i++) f[i][0]=g[i].s;for(int j=1;j<=h;j++){//预处理ST表int k=n-(1<<j)+1;for(int i=1;i<=k;i++){f[i][j]=max(f[i][j-1],f[i+(1<<(j-1))][j-1]);}}for(int i=1;i<=n;i++) sum[i]=sum[i-1]+g[i].f;int x=lower_bound(sum+1,sum+n+1,m)-sum;for(int i=x;i<=n;i++){int y=upper_bound(sum+1,sum+1+n,sum[i]-m)-sum;if(lmax(y,i)<ans) ans=lmax(y,i);}cout<<ans;return 0;
}