CodeForces 589F Gourmet and Banquet

给你N(1<=N<=100)个区间 l-r 求最大的子区间大小使每个区间都有这个子区间且覆盖不重复

做法 输入的时候纪录区间最大值 然后二分求答案 

#include<stdio.h>
#include<stdlib.h>
#include<string.h>
#include<iostream>
#include<algorithm>
using namespace std;
#define MAXN 101
#define MAX 10001
#define IMAX 2147483647
struct DISH{int a,b;}a[MAXN];
int N,Left=0,Right=0,ans=0;
bool vis[MAX];
bool cmp(DISH X,DISH Y){return X.b<Y.b;}
bool check(int time_per_dish)
{
    memset(vis,false,sizeof(vis));
    for(int i=1;i<=N;i++)
    {
          if(a[i].b-a[i].a<time_per_dish)   return false;
          int occupy=0;
          for(int j=a[i].a;j<a[i].b;j++)
                  if(!vis[j])//vis[j]表示j->j+1的时间是否被占用 
                  {
                        occupy++;
                        vis[j]=true;
                        if(occupy==time_per_dish)   break;
                }
          if(occupy<time_per_dish)   return false;
    }
    return true;
}
int main()
{
#ifndef ONLINE_JUDGE 
      freopen("input.txt","r",stdin); 
      freopen("output.txt","w",stdout); 
#endif 
    scanf("%d",&N);
    for(int i=1;i<=N;i++)
    {
          scanf("%d%d",&a[i].a,&a[i].b);
          Right=max(Right,a[i].b-a[i].a);
    }
    sort(a+1,a+1+N,cmp);
    while(Left<=Right)
    {
          int middle=(Left+Right)>>1;
          if(check(middle))
          {
                  Left=middle+1;
                  ans=max(middle,ans);
          }
          else  Right=middle-1;
          
    }
    printf("%d
",ans*N);
    return 0;
}