CodeForces 589F Gourmet and Banquet 题解

In the first example the gourmet eats the second dish for one second (from the moment in time 1 to the moment in time 2), then he eats the first dish for two seconds (from 2 to 4), then he returns to the second dish for one second (from 4 to 5). After that he eats the third dish for two seconds (from 6 to 8).

In the second example the gourmet cannot eat each dish for at least one second because there are three dishes but they are available for only one second (from 1 to 2).

【分析】：

此题很像是另类的求最大不相交区间的题目，之前写过求最大不相交区间的文章，了解详情戳此：点击打开链接

也就是相当于，每个区间都要取到，求每个区间取相同长度时，能取到的总长度的最大值。

参考求最大不相交区间的贪心法的做法，这里的做法如下：现将时间段按b排序（与求最大不相交区间相同），由于是要求总时间最大，也就是求每段区间能取的时间的最大值，且最大值满足单调性质（随每段区间能取的时间，总时间增加，即答案增加，亦即存在不满足题设条件和满足题设条件的唯一分界点），故我们可以用二分答案的方法举出每段区间能取的时间，判断是否合法的方法是从前往后地根据之前排好序了的菜品顺序去取时间，如果无法达到举出的时间就不合法，否则合法。

【代码】：

#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\n",ans*N);return 0;
}