程序设计思维与实践
9 minutes read (About 1339 words)

程设Week14-模拟

又是时间模拟—、—

题目描述

众所周知，TT家里有一只魔法喵。这只喵十分嗜睡。一睡就没有白天黑夜。喵喵一天可以睡多次！！每次想睡多久就睡多久╭(╯^╰)╮

喵睡觉的时段是连续的，即一旦喵喵开始睡觉了，就不能被打扰，不然喵会咬人哒[○･｀Д´･ ○]

可以假设喵喵必须要睡眠连续不少于 A 个小时，即一旦喵喵开始睡觉了，至少连续 A 个小时内（即A*60分钟内）不能被打扰！

现在你知道喵喵很嗜睡了，它一天的时长都在吃、喝、拉、撒、睡，换句话说要么睡要么醒着滴！

众所周知，这只魔法喵很懒，和TT一样懒，它不能连续活动超过 B 个小时。

猫主子是不用工作不用写代码滴，十分舒适，所以，它是想睡就睡滴。

但是，现在猫主子有一件感兴趣的事，就是上BiliBili网站看的新番。

新番的播放时间它已经贴在床头啦（每天都用同一张时间表哦），这段时间它必须醒着！！

作为一只喵喵，它认为安排时间是很麻烦的事情，现在请你帮它安排睡觉的时间段。

输入

多组数据，多组数据，多组数据哦，每组数据的格式如下：

第1行输入三个整数，A 和 B 和 N (1 <= A <= 24, 1 <= B <= 24, 1 <= n <= 20)

第2到N+1行为每日的新番时间表，每行一个时间段，格式形如 hh:mm-hh:mm (闭区间)，这是一种时间格式，hh:mm 的范围为 00:00 到 23:59。注意一下，时间段是保证不重叠的，但是可能出现跨夜的新番，即新番的开始时间点大于结束时间点。
保证每个时间段的开始时间点和结束时间点不一样，即不可能出现类似 08:00-08:00 这种的时间段。时长的计算由于是闭区间所以也是有点坑的，比如 12:00-13:59 的时长就是 120 分钟。
不保证输入的新番时间表有序。

输出

我们知道，时间管理是一项很难的活，所以你可能没有办法安排的那么好，使得这个时间段满足喵喵的要求，即每次睡必须时间连续且不少于 A 小时，每次醒必须时间连续且不大于 B 小时，还要能看完所有的番，所以输出的第一行是 Yes 或者 No，代表是否存在满足猫猫要求的时间管理办法。

然后，对于时间管理，你只要告诉喵喵，它什么时候睡觉即可。
即第2行输出一个整数 k，代表当天有多少个时间段要睡觉
接下来 k 行是喵喵的睡觉时间段，每行一个时间段，格式形如 hh:mm-hh:mm (闭区间)，这个在前面也有定义。注意一下，如果喵喵的睡眠时段跨越当天到达了明天，比如从23点50分睡到0点40分，那就输出23:50-00:40，如果从今晚23:50睡到明天早上7:30，那就输出23:50-07:30。

输出要排序吗？（输出打乱是能过的，也就是说，题目对输出的那些时间段间的顺序是没有要求的）

哦对了，喵喵告诉你说，本题是 Special Judge，如果你的输出答案和 Sample 不太一样，也可能是对的，它有一个判题程序来判定你的答案（当然，你对你自己的答案肯定也能肉眼判断）

题目分析

  • 原则：能睡就睡，否则不睡。

  • 跨天的处理：直接在第二天的时间上加上24h

  • 最后一个事件的结束时间与第一个事件的开始时间中间事件段的处理：把第一个事件作为n+1个事件加24h然后加到序列末尾。

  • 坑点：

    • 不能24h不睡，因为和第二天连起来就是48h不睡，和第三天连起来就是。。永远不睡，必然是不存在的。
    • 睡觉区间是闭区间，因此要注意+1-1

  • 小tips：

    printf("%02d:%02d-%02d:%02d\n",...)用于控制输出，香！

代码

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
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
#include<iostream>
#include<cstring>
#include<algorithm>
using namespace std;
struct event{
    int begin,end;
    int t;
    event(int b,int e):begin(b),end(e){}
    event(){begin = end = t = 0;}
}avi[50],slp[50];
bool cmp(event& a,event& b){
    return a.begin < b.begin;
}
int scnt;
int main(){
    int A,B,k;
    while(~scanf("%d%d%d",&A,&B,&k)){
        scnt = 0;
        A *= 60,B *= 60;
        memset(slp,0,sizeof(slp));
        memset(avi,0,sizeof(avi));
        int sh,sm,eh,em;
        bool flag = true;
        for(int i = 0;i<k;i++){
            scanf("%d:%d-%d:%d",&sh,&sm,&eh,&em);
            avi[i] = event(sh*60+sm,eh*60+em);
            if(avi[i].end < avi[i].begin) avi[i].end += 24*60;
        }
        sort(avi,avi+k,cmp);
        avi[k] = event(avi[0].begin + 24 * 60 , avi[0].end + 24 * 60);
        for(int i = 1;i<=k;i++){
            if(avi[i].begin -1 - avi[i-1].end >= A ){
                slp[scnt++] = event(avi[i-1].end + 1,avi[i].begin - 1);
            }
        }
        slp[scnt] = event(slp[0].begin + 24 * 60,slp[0].end + 24 * 60);
        for(int i = 1; i<=scnt;i++){
            if(slp[i].begin - 1 - slp[i-1].end > B) {flag = false;break;}
        }
        if(!flag || scnt == 0 ) {
            cout<<"No\n";
            continue;
        }else {
            cout<<"Yes\n"<<scnt<<"\n";
            for(int i = 0;i<scnt;i++){
                slp[i].begin += 24*60;
                slp[i].begin %= 24*60 ;
                slp[i].end += 24*60;
                slp[i].end %= 24*60;
                printf("%02d:%02d-%02d:%02d\n",slp[i].begin / 60,slp[i].begin % 60,slp[i].end / 60 ,slp[i].end % 60);
            }
        }
    }
}
# 模拟
程设Week16-模拟
程设Week12-作业
Follow
Your browser is out-of-date!

Update your browser to view this website correctly. Update my browser now

×