金牌厨师

金牌厨师

tag：

• 二分 前缀 差分
• 1900

题意： 有m个人，每个人可以拥有l-r区间的忍受值，k为选出的人，x为这些人可以忍受的最大区间。求min(k,x)的最大值。

求最小的最大，铁二分题了。

连续二字，必须要考虑到前缀和差分的相关性，可能可以成为突破口。

解： 二分答案，二分的主体是忍受范围的区间。其实这点是很难想到的。我们知道，如果考虑二分的人，是很难确定选择哪些人，但是如果把问题转变成二分容忍区间，就可以利用上差分的作用，创建出一些小的连续区间，代表在这些区间内，存在某些人的容忍度可行。

example：

  ve[x[i].first + mid - 1] ++ ;
  ve[x[i].second + 1] --;

这样的差分就可以创建一个小小的区间代表当范围为mid时，他的最大承受辣度范围可以是这个区间。

代码实现如下

#include<bits/stdc++.h>
using namespace std;
const int maxn = 1e6+7;
pair<int,int>x[maxn];
 int main (){
     int n ,m;
     cin >> n >> m;
     for(auto i = 1; i<= m ; i++) cin >> x[i].first >> x[i].second;
     sort(x+1,x+1+m);
     int l = 0 , r = n+1;
     int ans = 0;
     while(l < r) {
         vector<int>ve(n+2);
         int mid = l + r >> 1;
        // int sl = mid, sr = 0x3f3f3f3f;
         int cnt = 0;
         for(auto i = 1; i <= m ; i++) {
             if(x[i].second - x[i].first + 1 < mid)continue;
             ve[x[i].first + mid - 1] ++ ;
             ve[x[i].second + 1] --;
         }

         for(int i =1 ;i <= n ; i++) ve[i] += ve[i - 1],cnt = max(cnt,ve[i]);
         if(cnt >= mid) {
             l = mid + 1;
             ans = max(ans,mid);
         }else{
             r = mid;
             ans = max(ans,cnt);
         }
     }
     cout<<ans<<"\n";
 }