[USACO 2017 Dec G]Haybale Feast

The first line contains the integers N and M, the number of haybales and the minimum total flavor the meal must have, respectively. The next N lines describe the N haybales with two integers per line, first the flavor F and then the spiciness S.

C++14(g++5.4) 解法, 执行用时: 78ms, 内存消耗: 3860K, 提交时间: 2020-08-09 10:59:18

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=1e5+5;
int n;
ll m,a[N],b[N];
bool check(ll x){
    ll sum=0;
    for(int i=0;i<n;i++){
        if(b[i]>x){
            sum=0;
            continue;
        }
        sum+=a[i];
        if(sum>=m) return 1;
    }
    return 0;
}

int main()
{
    cin>>n>>m;
    for(int i=0;i<n;i++) cin>>a[i]>>b[i];
    ll l=0,r=1e18;
    while(l<=r){
        ll mid=l+r>>1;
        if(check(mid)) r=mid-1;
        else l=mid+1;
    }
    cout<<l<<endl;
	return 0;
}

C++11(clang++ 3.9) 解法, 执行用时: 31ms, 内存消耗: 1528K, 提交时间: 2020-09-29 17:22:19

#include<bits/stdc++.h>
#define LL long long
using namespace std;
const int N=1e5+5,Inf=2e9;
int n,b[N],que[N],ans=Inf;
LL m,a[N];
int main(){
	scanf("%d%lld",&n,&m);
	for(int i=1;i<=n;i++)scanf("%lld%d",&a[i],&b[i]),a[i]+=a[i-1];
	LL L=1,R=0;
	for(int r=1,l=1;r<=n;r++){
		while(L<=R&&b[que[R]]<=b[r])R--;
		que[++R]=r;
		while(a[r]-a[l-1]>=m){
			if(L<=R)ans=min(ans,b[que[L]]);
			while(que[L]<=l)L++;l++;
		}
	}
	printf("%d\n",ans);
	return 0;
}

详情