0%

Haybale Feast

发表于 Valine：
本文字数： 818 阅读时长 ≈ 1 分钟

链接：https://ac.nowcoder.com/acm/contest/625/C
来源：牛客网

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
#include <bits/stdc++.h>
using namespace std;
const int maxn=1e5+5;
const int INF=0x3f3f3f3f;
typedef long long ll;
int n;
ll m;
int f[maxn];
int s[maxn];
int p[maxn];
int head=1,tail=0;
int ind=1;


int main(){

    //freopen("data.in","r",stdin);

    scanf("%d%lld",&n,&m);
    for(int i=1;i<=n;i++) scanf("%d%d",&f[i],&s[i]);
    ll sum=0;
    ll ans=INF;
    for(int i=1;i<=n;i++)
    {
        sum+=f[i];
        while(ind<=i&&sum-f[ind]>=m){
            sum-=f[ind]; ind++;         //找到满足条件的ind位置
        }
        while(head<=tail&&p[head]<ind) head++;          //当队首的位置小于ind位置，队首出队
        while(head<=tail&&s[p[tail]]<=s[i]) tail--;    //当 当前元素大于队尾，出队
        p[++tail]=i;                                //入队
        if(sum>=m) ans=min(ans,(ll)s[p[head]]);     //当满足条件时，求最优解
    }
    printf("%lld\n",ans);

    return 0;
}
-------------本文结束感谢您的阅读-------------