Each cases has a positive integer n(1<=n<=10000), which means n groups of customer. Then following n lines, each line there is a positive integer Xi(1<=Xi<=100), referring to the sum of the number of the ith group people, and the arriving time STi and departure time Edi(the time format is hh:mm, 0<=hh<24, 0<=mm<60), Given that the arriving time must be earlier than the departure time.
Pay attention that when a group of people arrive at the restaurant as soon as a group of people leaves from the restaurant, then the arriving group can be arranged to take their seats if the seats are enough.
2 2 6 08:00 09:00 5 08:59 09:59 2 6 08:00 09:00 5 09:00 10:00
11 6
这道题目很容易想到用线段树更新，比赛的时候也确实用线段树过了，但实际上用线段树更新有些大材小用，因为题目只需查询一次，并没有动态更新和动态查询。
可以用一个sum数组记录该点总共的人数，输入的时候可预处理第i批客人的变化情况。来的时候 sum[i]就加上相应的人数，走的时候sum[i]就减去相应的人数。
可以得到地推公式 sum[i] += sum[i-1]; i表示时间的推移，从第0分钟一直可以推到结束时间。因为期间不用再次更新也无需查询，这种算法要比线段树更具优势。
#include#include #include #include #include #define lson o<<1, l, m #define rson o<<1|1, m+1, r using namespace std; typedef long long LL; const int maxn = 1500; const int MAX = 0x3f3f3f3f; const int mod = 1000000007; int t, n; int sum[maxn]; int main() { scanf("%d", &t); while(t--) { scanf("%d", &n); memset(sum, 0, sizeof(sum)); for(int i = 0; i < n; i++) { int tmp, h1, m1, h2, m2; scanf("%d %d:%d %d:%d", &tmp, &h1, &m1, &h2, &m2); int st = h1*60+m1; int en = h2*60+m2; sum[st] += tmp; sum[en] -= tmp; } int ans = sum[0]; for(int i = 1; i <= 1440; i++) { sum[i] += sum[i-1]; ans = max(ans, sum[i]); } printf("%d\n", ans); } return 0; }