P4085 [USACO17DEC] Haybale Feast G 题解

Colubrid_L · 2026-01-23 19:17:49 · 题解

前置芝士

单调栈、前缀和。

思路

先对风味进行前缀和，前缀和数组可以设为 val_i。

既然一个区间的辣度是这个区间的最大辣度，那我们不妨对每一个位置 i，找到它左边第一个比它大的位置的后一个位置（不能包含比它大的） pre_i 和它右边第一个比它大的前一个位置 nxt_i。那么这段区间的辣度就是 s_i，其风味就是 val_{nxt_i}-val_{pre_i-1}。

最后再用一个 O(n) 的循环判断位置 i 是否符合条件，即 m\le val_{nxt_i}-val_{pre_i-1}，若符合，则与当前答案取最小。

看到这里，应该能直接想到该用什么算法维护 pre 和 nxt。没错是单调栈，从前往后做一遍，再从后往前做一遍，分别记住就可以了。这一段的时间复杂度是 O(n)。

综上，按此做法可以做到 O(n) 的时间复杂度。

代码

//written by Colubrid_L
#include<bits/stdc++.h>
using namespace std;
#define int long long
const int N=1e5+5;
struct node {
    int s,val;
}a[N];
int n,m,tp,st[N],pre[N],nxt[N],val[N],ans=INT_MAX;
signed main(){
    ios::sync_with_stdio(false);
    cin.tie(0),cout.tie(0);
    cin>>n>>m;
    for(int i=1;i<=n;i++)
        cin>>a[i].s>>a[i].val,val[i]=val[i-1]+a[i].s;
    st[tp=1]=1;
    for(int i=2;i<=n;i++){
        while(tp>=1&&a[st[tp]].val<=a[i].val) tp--;
        pre[i]=!tp?1:st[tp]+1;
        st[++tp]=i;
    }
    st[tp=1]=n;
    for(int i=n-1;i>=1;i--){
        while(tp>=1&&a[st[tp]].val<=a[i].val) tp--;
        nxt[i]=!tp?n:st[tp]-1;
        st[++tp]=i;
    }
    pre[1]=1,nxt[n]=n;
    for(int i=1;i<=n;i++)
        if(val[nxt[i]]-val[pre[i]-1]>=m)
            ans=min(ans,a[i].val);
    cout<<ans<<'\n';
    return 0;
}