有m盘菜，每盘有一个开始时间和结束时间，必须每盘都吃同样的时间。问最多能吃多久。
二分答案，然后用一个优先队列维护当前时间内的菜，然后每次都吃结束时间最小的那盘。
1 #include <cstdio> 2 #include <algorithm> 3 #include <cstring> 4 #include <queue> 5 6 using namespace std; 7 8 const int maxn = 1e4+10; 9 const int INF = 0x3f3f3f3f; 10 int N,len,a[maxn],b[maxn],save[200];; 11 12 struct node 13 { 14 int a,b,id; 15 node(){} 16 node(int x,int y,int z):a(x),b(y),id(z){} 17 bool operator < (const node &b) const 18 { 19 return a<b.a; 20 } 21 }Dish[maxn]; 22 23 struct node2 24 { 25 int ed,id; 26 node2(int x,int y):ed(x),id(y){} 27 bool operator < (const node2 &b) const 28 { 29 return ed > b.ed; 30 } 31 }; 32 33 int solve(int ll,int rr) 34 { 35 int mid = (ll+rr)>>1,cnt=0; 36 if(ll+1 >= rr) return mid; 37 priority_queue<node2> q; 38 39 memset(save,0,sizeof save); 40 //printf("ll:%d rr:%d\n",ll,rr); 41 for(int cur=0;cur<=len;cur++) 42 { 43 //printf("cur:%d cnt:%d num:%d\n",cur,cnt,q.size()); 44 while(cnt < N && Dish[cnt].a == cur) 45 { 46 q.push(node2(Dish[cnt].b,Dish[cnt].id)); 47 cnt++; 48 } 49 //printf("save:%d mid:%d\n",save[q.top().id],mid); 50 while(!q.empty() && save[q.top().id]>=mid && save[q.top().id]) 51 { 52 q.pop(); 53 } 54 55 if(!q.empty()) {/*printf("id:%d++\n",q.top().id);*/save[q.top().id]++;} 56 57 while(!q.empty() && q.top().ed <= cur+1) 58 { 59 if(save[q.top().id] < mid || save[q.top().id]==0) {/*printf("id:%d save:%d\n",q.top().id,save[q.top().id]);*/return solve(ll,mid==0?0:mid);} 60 q.pop(); 61 } 62 63 if(q.empty()&&cnt==N) return solve(mid,rr); 64 } 65 } 66 67 int main() 68 { 69 scanf("%d",&N); 70 int l = INF,r = -INF; 71 len = -INF; 72 for(int i=0;i<N;i++) 73 { 74 scanf("%d%d",&a[i],&b[i]); 75 Dish[i] = node(a[i],b[i],i); 76 r = max(b[i]-a[i],r); 77 len = max(len,b[i]); 78 } 79 sort(Dish,Dish+N); 80 printf("%d\n",solve(0,r+1)*N); 81 }