题意是有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; }