【二分】Haybale Feast

题目来源：牛客

题目大意：

N（N<$10^5$）种饲料，每种饲料有flavor和spiciness两个参数（各自用一个$10^9$内的整数表示）

N种饲料编号1~N，从中选出连续的一组饲料（比如[3,7]号饲料），这组饲料总的spiciness值为该组内各个饲料spiciness值的最大值，总的flavor值为该组内各个饲料flavor值的和

现求从N种饲料中取出的连续的一组饲料，在满足flavor值大于M（M<$10^{18}$）的前提下，spiciness的最小值为多少

分析：

二分，然后$O(n)$判断解是否满足要求

二分的思路来源：答案的范围为$[1,10^9]$，且若有两个满足要求的解，值小的一定比值大的更优

如何判断解是否满足要求？

遍历一遍数组，利用贪心的思想，若一种饲料spiciness值小于等于x，则我们就将它的flavor值加上（因为目的是得到sum值大于M的区间）

代码：

#include <cstdio>
#include <iostream>
#include <algorithm>
#include <string>
#include <vector>
#include <cmath>
using namespace std;

long long N,M;
long long a[100005],b[100005];

bool check(long long x){
  long long sum=0;
  for(int i=1;i<=(int)N;i++){
      if(b[i]>x){
         sum=0;
         continue;
      }
      sum+=a[i];
      if(sum>=M) return true;
  }
  return false;
}

int main(){
  scanf("%lld%lld",&N,&M);
  for(int i=1;i<=(int)N;i++)
      scanf("%lld%lld",&a[i],&b[i]);
  long long l=1,r=(long long )1e9+1;
  long long ans;
  while(l<=r){
     long long mid=(r-l)/2+l;
     if(check(mid)) ans=mid,r=mid-1;
     else l=mid+1;
  }
  printf("%lld\n",ans);
  return 0;
}