题目链接
思路；
该题的思路,类似于区间求差问题,将每个组的用餐时间转化为一个区间,全部都放在一个数轴上,维护一个座位的值,标记区间左右端点,遇见左区间+座位遇到右区间-座位,维护最优解即可.
wa了无数发。。。。才想起这种做法。。。。
#include<bits/stdc++.h> using namespace std; typedef long long ll; const int maxm=1e4+10; const int maxn=2222; struct node { int num; int time; int flag; }q[2*maxm]; int cmp(node a,node b) { if(a.time!=b.time) return a.time<b.time; return a.flag>b.flag; } int n; int change(char * z) { int ans=0,ans2=0; int flag=0; int len=strlen(z); for(int i=0;i<len;i++) { if(z[i]==':') flag=1; if(flag==1&&z[i]!=':') { ans2=ans2*10+z[i]-'0'; } if(flag==0) { ans=ans*10+z[i]-'0'; } } return ans*60+ans2; } int main() { int t; scanf("%d",&t); while(t--) { scanf("%d",&n); char s[111]; for(int i=1;i<=2*n;i+=2) { scanf("%d",&q[i].num); //ss=max(ss,q[i].num); scanf("%s",s); q[i].time=change(s); q[i].flag=1; scanf("%s",s); q[i+1].num=q[i].num; q[i+1].time=change(s); q[i+1].flag=2; } sort(q+1,q+1+2*n,cmp); int ss=0; int ans=0; for(int i=1;i<=2*n;i++) { if(q[i].flag==1) { ss+=q[i].num; } else ss-=q[i].num; ans=max(ss,ans); } printf("%d\n",ans); } return 0; } Marcus-Bao 认证博客专家 推荐系统 ACM算法竞赛 机器学习 本科毕业于国内知名四非大学，现中国科学院大学博士生，中国科学院计算技术研究所vipl实验室，老年ACM铁牌退役选手，喜欢算法竞赛，会点数据结构和算法，熟悉c++，python等；现阶段研究方向主要为机器学习与数据挖掘，比较关注推荐系统，发过顶会，炼过丹，平时博客主要记录些关于算法、数据结构，人工智能技术以及平时看的论文总结分享等，欢迎大家关注我，一起多多交流共同进步！
