MYF

HDU 4883 TIANKENG’s restaurant

题目链接

HDU 4883

方法:通过改两个点达到更改两个区间的目的

题目分析

题目大意

总共有n伙人去排队吃饭,每伙有g个人,给出到达时间和离开时间,问店主最少需要准备多少椅子。

解析

这题受HDU1556的启发,本来用树状数组做,以为很优越,但是最后遍历每个点的时候计算sum复杂度太高,会T掉。干脆换普通数组,每次改两个点,然后从头到尾遍历一遍即可。时间上看起来还是比较优越的。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
#include <algorithm>
#include <iostream>
#include <cstdio>
#include <cstring>
using namespace std;
#define maxn 1500
int c[maxn],n;
int node[maxn];
int main(){
int t;
scanf("%d",&t);
while(t--)
{
memset(c,0,sizeof(c));
memset(node,0,sizeof(node));
int n,ans=0,cnt=0;
cin>>n;
int h,hh,m,mm,tmp,g;
for(int i=0;i<n;i++){
scanf("%d %d:%d %d:%d",&g,&h,&m,&hh,&mm);
tmp=h*60+m;
node[tmp]+=g;
tmp=hh*60+mm;
node[tmp]-=g;
}
int total=0;
for(int i=0;i<maxn;i++)
{
total+=node[i];
ans=max(total,ans);
}
cout<<ans<<endl;
}
}