学步园

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

大意：中文

解法：

才50W,排序N*logN，然后模拟，这完全不会超嘛，看有的人用线段树做。。。好吧，我现在还不会线段树，正准备学。

以起始时间排序，然后以结束时间更新，模拟一遍A过，不枉我大晚上的还在水，然后我在discuss里看到个超短的代码，看不懂的说，囧。。。也一起贴下

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
const int maxn=5e5+100;
struct node
{
    int hs,ms,he,me;
    node(){hs=ms=he=me=0;}
    bool operator <  (const node &a) const {
        return hs<a.hs || ((hs==a.hs)&&ms<a.ms);
    }
}t[maxn];

bool work (node a,node b) //比较前一个的结束时间是否比后一个的开始时间晚
{
    if(a.he>b.hs) return true;
    else if(a.he<b.hs) return false;
    if(a.me>=b.ms) return true;
    return false;
}

bool work2 (node a,node b) //比较前一个的结束时间是否比后一个的结束时间晚
{
    if(a.he>b.he) return true;
    else if(a.he<b.he) return false;
    if(a.me>=b.me) return true;
    return false;
}

int work3 (node a,node b) //前者的结束与后者的开始有间隙
{
    int h,m;
    m=b.ms-a.me;
    if(m<0) {m=(m+60)%60; h=b.hs-a.he-1;}
    else h=b.hs-a.he;
    return h*60+m;
}

int main()
{
    int n;
    while (scanf("%d",&n)==1)
    {
        for(int i=0;i<n;i++)
            scanf("%d:%d %d:%d",&t[i].hs,&t[i].ms,&t[i].he,&t[i].me);
        sort(t,t+n);
        int s=0;
        node temp=t[0];
        s=t[0].hs*60+t[0].ms;

        for(int i=1;i<n;i++)
        {
            if(!work(temp,t[i]) )
                s+=work3(temp,t[i]);

            if(!work2(temp,t[i]) )  temp=t[i];

        }
        s+=60-temp.me;
        temp.he++;
        s+=60*(24-temp.he);
        printf("%d\n",s);
    }
    return 0;
}

这代码转自：http://acm.hdu.edu.cn/discuss/problem/post/reply.php?postid=11689&messageid=1&deep=0

#include<stdio.h>
#include<string.h>
int a[24*60+5];
int main()
{
    int n,i,sum,j,c,d,e,f,s1,s2;
    while(scanf("%d",&n)!=EOF)
    {
        sum=24*60;
        memset(a,0,sizeof(a));
        for(i=0;i<n;i++)
        {
            scanf("%d:%d %d:%d",&c,&d,&e,&f);
            s1=(c*60+d);
            s2=(e*60+f);
            for(j=s1;j<s2;j++)
            {
                if(!a[j])
                {
                    sum--;
                    a[j]=1;
                }
            }
        }
        printf("%d\n",sum);
    }
    return 0;
}