题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=4883
#include<iostream> #include<cstdio> #include<algorithm> #include<queue> #include<vector> using namespace std; const int N=10005; int n; // group数量 struct node { int sh,sm; int eh,em; int num; }g[N]; // 比较两个时间的先后 int Compare(int h1,int m1,int h2,int m2) { if(h1>h2) return 1; else if(h1<h2) return -1; if(m1>m2) return 1; else if(m1<m2) return -1; return 0; } // 按开始时间排序 bool cmp(node a,node b) { if(a.sh!=b.sh) return a.sh<b.sh; else return a.sm<b.sm; } // 按结束时间排序 bool operator< (node a,node b) { if(a.eh!=b.eh) return a.eh>b.eh; else return a.em>b.em; } void Input() { cin>>n; for(int i=0;i<n;i++){ scanf("%d",&g[i].num); scanf("%d:%d",&g[i].sh,&g[i].sm); scanf("%d:%d",&g[i].eh,&g[i].em); } sort(g,g+n,cmp); // for(int i=0;i<n;i++){ // printf("%d ",g[i].num); // printf("%d:%d ",g[i].sh,g[i].sm); // printf("%d:%d\n",g[i].eh,g[i].em); // } } void solve() { priority_queue<node>q; int Max=0; // 最大椅子数; int M=0; // 剩余可以用的椅子; for(int i=0;i<n;i++){ // 归还已经使用完的椅子; while(!q.empty()){ node tmp=q.top(); if(Compare(tmp.eh,tmp.em,g[i].sh,g[i].sm)<=0){ M+=tmp.num; q.pop(); }else break; } // 新来用户使用椅子; if(M<g[i].num){ // 需要新添椅子 Max+=g[i].num-M; M=0; }else{ // 不需要新添椅子 M-=g[i].num; } q.push(g[i]); } cout<<Max<<endl; } int main() { int t; cin>>t; while(t--){ Input(); solve(); } return 0; } /* 2 4 8:00 8:01 5 8:00 8:01 */