HDU 4883 TIANKENG’s restaurant

题目链接

HDU 4883

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

题目分析

题目大意

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

解析

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

代码

#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;
    }
}