hdu4883-TIANKENG’s restaurant(简单贪心)

发布于 2019-07-19  981 次阅读


问题传送门:

题意:

有n组人去吃饭,下面n行

对应每组人的人数,到达时间和离开时间

求餐厅最少需要多少椅子。

分析:

也就是求 同时在餐厅的人数 最多是多少。

把所有的时间升序排序,遍历一遍。

如果是到达时间,加入人数

如果是离开时间,减去人数

维护一个最大值
一开始,时间用的是string 类型, 直接对str 排序, 所用的时间太长。

无奈,转换为数值。

代码:

#include <iostream>
#include <algorithm>
#include <cstdio>
#include <cmath>

using namespace std;

typedef long long LL;

const int MAXN = 2e4+10;

struct Node
{
    int isin;
    int num;
    int tim;
}a[MAXN];


bool cmp(Node a, Node b)
{
    if (a.tim != b.tim)
        return a.tim < b.tim;
    return a.isin < b.isin;
}

int main()
{
    int T, tnum, cnt, ans;
    int in1, in2, ot1, ot2;
    cin >> T;
    while (T--)
    {
        int n, tans;
        cnt = 0, ans = 0, tans = 0;
        cin >> n;
        for (int i = 0; i < n; i++)
        {
            scanf("%d %d:%d %d:%d",&tnum,&in1,&in2,&ot1,&ot2);
            a[cnt].tim = in1*60+in2; a[cnt].num = tnum; a[cnt++].isin = 1;
            a[cnt].tim = ot1*60+ot2; a[cnt].num = tnum; a[cnt++].isin = 0;
        }
        sort(a, a+cnt, cmp);
        for (int i = 0; i < cnt; i++)
        {
            if (a[i].isin){
                tans += a[i].num;
                ans = max(ans, tans);
            }
            else
                tans -= a[i].num;
        }
        printf("%d\n",ans);
    }
    return 0;
}



Simple And Clear