CF 589F 贪心+二分

题意是有N道菜，需要吃到每一种菜，且每种菜要吃相同时间。

那么按时间右端点排序，再依次有空则吃。为什么这样贪心是正确的呢，因为选择更早结束的菜，那么之后就会剩下更多的时间去吃其余的菜，那么贪心是正确的。

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
const int maxn=110;
int n;
bool vis[10010];
struct node
{
    int a,b;
    bool operator<(const node &x) const
    {
        return b<x.b;
    }
}t[maxn];
bool check(int mid)
{
    //memset(vis,0,sizeof(vis));
    for(int i=0;i<10010;i++)
    {
        vis[i]=false;
    }
    for(int i=1;i<=n;i++)
    {
        if(t[i].b-t[i].a<mid) return false;
        int cnt=0;
        for(int j=t[i].a;j<t[i].b;j++)
        {
            if(cnt>=mid) break;
            if(!vis[j])
            {
                vis[j]=true;
                cnt++;
            }
        }
        if(cnt<mid) return false;
    }
    return true;
}

int bin(int l,int r)
{
    int ans=l;
    while(l<=r)
    {
        int mid=(l+r)>>1;
        if(check(mid))
        {
            ans=mid;
            l=mid+1;
        }
        else
            r=mid-1;
    }
    return ans;
}

int main()
{
    while(~scanf("%d",&n))
    {
        for(int i=1;i<=n;i++)
        {
            scanf("%d%d",&t[i].a,&t[i].b);
        }
        sort(t+1,t+1+n);
        printf("%d\n",bin(0,t[n].b)*n);
    }
    return 0;
}