首页 > ACM题库 > HDU-杭电 > hdu 3700 Cat[解题报告]C++
2015
02-21

hdu 3700 Cat[解题报告]C++

Cat

问题描述 :

There is a cat, cat likes to sleep.
If he sleeps, he sleeps continuously no less than A hours.
For some strange reason, the cat can not stay awake continuously more than B hours.
The cat is lazy, it could sleep all the time,
but sometimes interesting events occur(such as cat food, TV show, etc) .
The cat loves these events very much.
So, Please help the cat plan their day so as not to miss any interesting events.
Every day the cat wants to live on the same schedule.

输入:

The first line of the input file contains two integers A and B (1 <= A, B <= 24).
The second line of the input file contains the number n, the number of interesting events (1 <= n <= 20).
Following n rows describe the interesting events.
Each event is described line of the form hh:mm-hh:mm, which specifies
the time period during which it occurs. Time varies from 00:00 to 23:59.
No two interesting events will overlap.
If the event is completed earlier than the beginning, This means that it captures midnight.
The event is considered to be occupying the whole minute,
when it begins and the moment when it ends (event 12:00-13:59 lasted exactly 120 minutes). Start time and time end of the event are different.

输出:

The first line of the input file contains two integers A and B (1 <= A, B <= 24).
The second line of the input file contains the number n, the number of interesting events (1 <= n <= 20).
Following n rows describe the interesting events.
Each event is described line of the form hh:mm-hh:mm, which specifies
the time period during which it occurs. Time varies from 00:00 to 23:59.
No two interesting events will overlap.
If the event is completed earlier than the beginning, This means that it captures midnight.
The event is considered to be occupying the whole minute,
when it begins and the moment when it ends (event 12:00-13:59 lasted exactly 120 minutes). Start time and time end of the event are different.

样例输入:

12 12
1
23:00-01:00
3 4
3
07:00-08:00
11:00-11:09
19:00-19:59

样例输出:

Yes
1
01:07-22:13
No

#include<iostream>
#include<stdlib.h>
using namespace std;
#define N 21
int n,sleep,awake;
struct Time
{
    int hour;
    int minite;
    int sec;
    void trans()
    {        sec=hour*60+minite;    }
    void retrans()
    {        sec+=24*60;        }
    void minusonesecond()
    {
        if(minite==0)
            hour--,minite=59;
        else minite--;
        if(hour<0)
            hour+=24;
    }
    void addonesecond()
    {
        if(minite==59)
            hour++,minite=0;
        else minite++;
        if(hour>23)
            hour-=24;
    }
    bool operator < (const Time a)const
    {    
        if(hour==a.hour)
        {
            return minite<a.minite;
        }
        return hour<a.hour;        
    }
};

struct Arrange
{
    Time tb,te;
} affire[N];

int cmp(const void *a,const void *b)
{
    struct Arrange *A=(Arrange*)a;
    struct Arrange *B=(Arrange*)b;
    if(B->tb<A->tb)
        return 1;
    return -1;
}

Time sle[N][2];//sleep segment
char evn[20];

void solve(bool flag)
{
    int i,j,begin,end,temp=0,nowlast=0,segn=0;
    Time temp1,temp2;
    for(i=2;i<=n;i++)
    {
        end=affire[i].tb.sec-1;
        begin=affire[i-1].te.sec+1;
        if(end<begin&&begin-end!=1)
            end+=24*60;
        if(end-begin+1>=sleep)//can sleep
        {
            ++segn;
            temp1=affire[i-1].te;
            temp1.addonesecond();
            sle[segn][0]=temp1;
            temp1=affire[i].tb;
            temp1.minusonesecond();
            sle[segn][1]=temp1;
            nowlast=0;
        }
        else if(end-begin+1<sleep)//cannot sleep
        {
            if(nowlast==0)
                nowlast+=affire[i-1].te.sec-affire[i-1].tb.sec+1;
            nowlast+=affire[i].te.sec-affire[i-1].te.sec+1;
            if(nowlast>awake)
            {
                printf("No/n");
                return ;
            }
        }
    }
// [deal with the n-th and 1-st]
        end=affire[1].tb.sec-1;
        begin=affire[n].te.sec+1;
        if(end<begin&&begin-end!=1)
            end+=24*60;
        if(end-begin+1>=sleep)//can sleep
        {
            ++segn;
            temp2=affire[n].te;
            temp2.addonesecond();
            sle[segn][0]=temp2;
            temp1=affire[1].tb;
            temp1.minusonesecond();
            sle[segn][1]=temp1;
            nowlast=0;
        }
        else if(end-begin+1<sleep)//cannot sleep
        {
            if(nowlast==0)
                nowlast+=affire[n].te.sec-affire[n].tb.sec+1;
            nowlast+=affire[1].te.sec-affire[n].te.sec+1;
            if(nowlast>awake)
            {
                printf("No/n");
                return ;
            }
        }

    if(n==0)
    {
        segn=1;
        printf("Yes/n%d/n",segn);
        printf("00:00-23:59/n");
        return;
    }
    else
    {
        if(segn!=0)
        {
        printf("Yes/n%d/n",segn);
        for(i=1;i<=segn;i++)
        {
            printf("%02d:%02d-%02d:%02d/n",sle[i][0].hour,sle[i][0].minite,sle[i][1].hour,sle[i][1].minite);
        }
        }
        else
            printf("No/n");
    }
}

int main()
{
    while(scanf("%d%d",&sleep,&awake)!=EOF)
    {
        sleep*=60,awake*=60;
        scanf("%d",&n);
        int i,j;
        bool flag=false;
        bool ss=false;
        for(i=1;i<=n;i++)
        {
            Time T1,T2;
            scanf("%d:%d-%d:%d",&T1.hour,&T1.minite,&T2.hour,&T2.minite);
            T1.trans(),T2.trans();

            if(T2.sec-T1.sec+1>awake)
            {
                ss=true;
            }
            if(T2<T1)
            {
                flag=true;
                T2.retrans();
            }
            affire[i].tb=T1,affire[i].te=T2;
        }
        if(ss)
        {
            printf("No/n");
            continue;
        }
        qsort(affire+1,n,sizeof(Time)*2,cmp);
        solve(flag);//flag->是否跨午夜
    }
}

  1. 您没有考虑 树的根节点是负数的情况, 若树的根节点是个很大的负数,那么就要考虑过不过另外一边子树了