首页 > 代码库 > HDU 4883 TIANKENG’s restaurant

HDU 4883 TIANKENG’s restaurant

2024-07-14 09:28:01   222人阅读

题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=4883

解题报告：一家餐馆一天中有n波客人来吃饭，第 i 波  k 客人到达的时间是 s ，离开时的时间是e，求出餐馆最多的时候有多少人？

一开始我用线段树写的，但是RE了，后来看到一种方法，感觉很巧妙：一天时间全部转化成分钟，范围就是从0到1440，全部初始化为0，然后如果在s时间有k个

客人来的时候就在数组的s位置+k，然后在离开的时间e位置-k,最后扫一边数组，扫的过程中不断判断最大值。

 1 #include<cstdio> 2 #include<cstring> 3 #include<iostream> 4 #include<algorithm> 5 using namespace std; 6 const int maxn = 1500; 7 int que[maxn],T,n; 8  9 int main()10 {11     scanf("%d",&T);12     while(T--)13     {14         scanf("%d",&n);15         memset(que,0,sizeof(que));16         int d,s1,s2,e1,e2;17         while(n--)18         {19             scanf("%d %d:%d %d:%d",&d,&s1,&s2,&e1,&e2);20             s1 = 60 * s1 + s2;21             e1 = 60 * e1 + e2;22             que[s1] += d;23             que[e1] -= d;24         }25         int tot = 0,ans = 0;26         for(int i = 0;i <= 1440;++i)27         {28             tot += que[i];29             ans = max(ans,tot);30         }31         printf("%d\n",ans);32     }33     return 0;34 }
View Code

 


联系
我们