题目链接:http://acm.hdu.edu.cn/showproblem.php?pid=4883
解题报告:一家餐馆一天中有n波客人来吃饭,第 i 波 k 客人到达的时间是 s ,离开时的时间是e,求出餐馆最多的时候有多少人?
一开始我用线段树写的,但是RE了,后来看到一种方法,感觉很巧妙:一天时间全部转化成分钟,范围就是从0到1440,全部初始化为0,然后如果在s时间有k个
客人来的时候就在数组的s位置+k,然后在离开的时间e位置-k,最后扫一边数组,扫的过程中不断判断最大值。
#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;
const int maxn = ;
int que[maxn],T,n; int main()
{
scanf("%d",&T);
while(T--)
{
scanf("%d",&n);
memset(que,,sizeof(que));
int d,s1,s2,e1,e2;
while(n--)
{
scanf("%d %d:%d %d:%d",&d,&s1,&s2,&e1,&e2);
s1 = * s1 + s2;
e1 = * e1 + e2;
que[s1] += d;
que[e1] -= d;
}
int tot = ,ans = ;
for(int i = ;i <= ;++i)
{
tot += que[i];
ans = max(ans,tot);
}
printf("%d\n",ans);
}
return ;
}