CodeForces 589F 二分答案

【题目链接】
http://acm.hust.edu.cn/vjudge/contest/view.action?cid=106786#problem/B

【解题报告】
这道题目对我来说关键在于读对题意。
题意是：
有n盘菜，每道菜有一段可以吃的时间。the gourmet想要吃完所有n道菜，并且每道菜花的时间相同并且尽可能长，问你能不能做到。如果可以，输出吃这n道菜的总时间。
裸二分，二分枚举吃每道菜的时间即可。注意这里用到一个贪心思想，就是我们怎么来进行吃菜的最优方案。显然我们应该对每道菜的时间段进行右端点排序，然后按照时间顺序依次吃菜.这是因为每次我们都把对之后影响最少的菜吃掉，所以这个方案就是最优方案。

#include<bits/stdc++.h>
using namespace std;

const int maxn=1e5+100;

struct Node{
      int l,r;
      bool operator <(  const Node& rhs )const
      {
            return r<rhs.r ||( (r==rhs.r) && ( l<rhs.l )  );
      }
}a[maxn];

bool vis[maxn];
bool ok(  int x,int N )
{
      memset(vis,0,sizeof vis);
      for( int i=1;i<=N;i++ )
      {
            int cnt=0;
            for( int j=a[i].l+1;j<=a[i].r;j++  )if( !vis[j] )
            {
                  vis[j]=1;
                  if( ++cnt==x  )break;
            }
            if( cnt<x )return false;
      }
      return true;
}

int main()
{
      int N; cin>>N;
// build( 1,1,N );
      for( int i=1;i <=N; i++  ) cin>>a[i].l>>a[i].r;
      sort(  a+1,a+1+N );
      int L=1,R=1e5+1;
      while(  L<R-1 )
      {
            int mid=(L+R)/2;
            if( ok(mid,N)  )L=mid;
            else  R=mid;
      }
      if(ok(L,N))cout<<L*N<<endl;
      else cout<<0<<endl;

      return 0;
}