猫睡觉问题（模拟）c++,算法龙征天的博客-

问题描述

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

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

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

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

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

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

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

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

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

Input

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

第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 分钟。

Output

我们知道，时间管理是一项很难的活，所以你可能没有办法安排的那么好，使得这个时间段满足喵喵的要求，即睡必须不少于 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 不太一样，也可能是对的，它有一个判题程序来判定你的答案（当然，你对你自己的答案肯定也能肉眼判断）

Sample input

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

Sample output

Yes 1 01:07-22:13 No 

解题思路

这个题的思路比较简单，但是处理起来有些复杂。

思路是先把两个区间中间相隔的时间小于A的区间合并，这样剩下的睡觉时间都可以睡A小时（只剩一个区间需要特判一下）。

之后判断合并完毕的区间持续时间是否超过了B小时，如果超过，那就输出”No”，否则，输出剩下能睡觉的时间即可。

PS：我的代码存储小时和分钟，中间重载了运算符，所以会比较长，其实可以直接存储分钟，就是hour*60+minute，这样只在最终输出的时候转化一下格式，代码长度会大大减少。

完整代码

//#pragma GCC optimize(2) //#pragma G++ optimize(2) #include <iostream> #include <cstdio> #include <cstdlib> #include <cmath> #include <cstring> #include <string> #include <climits> #include <algorithm> #include <queue> #include <vector> using namespace std; struct timeNode{//时间节点 timeNode(int _h=0,int _min=0):h(_h),minute(_min){}     timeNode operator-(const timeNode& t){         timeNode tempt(h,minute); if(tempt<t){ tempt.h+=24; } if(tempt.minute<t.minute){ tempt.h-=1; tempt.minute+=60; }         tempt.minute-=t.minute; tempt.h-=t.h; return tempt; } bool operator<(const timeNode& t){ if(h<t.h) return true; else if(h>t.h) return false; else return minute<t.minute; } bool operator>(const timeNode& t){ if(h>t.h) return true; else if(h<t.h) return false; else return minute>t.minute; }     timeNode& operator=(const timeNode& t){ h=t.h; minute=t.minute; return *this; } int h,minute; }; timeNode& minus1min(timeNode& t){//减去一分钟     timeNode tempt=t; if(tempt.minute==0){ if(tempt.h==0) tempt.h+=24;         tempt.h--; tempt.minute+=60; }     tempt.minute--; return tempt; } timeNode& plus1min(timeNode& t){//加上一分钟     timeNode tempt=t;     tempt.minute+=1; if(tempt.minute==60){         tempt.minute=0; tempt.h++; } if(tempt.h==24) tempt.h=0; return tempt; } struct timeInterval{//时间区间 timeInterval(){} timeInterval(struct timeNode _st,struct timeNode _et){         startTime=_st; endTime=_et; }; bool operator<(const timeInterval& t){ return startTime<t.startTime; }     timeInterval& operator=(const timeInterval& t){ startTime=t.startTime; endTime=t.endTime; return *this;}     timeNode startTime,endTime; }; timeInterval tiInt[24]; int a,b,n,cnt; bool comp(timeInterval &_a,timeInterval &_b){ return _a<_b; } int main(){ while(scanf("%d %d %d",&a,&b,&n)!=EOF){         timeNode A(a,1),B(b-1,59);//这里是为了应对题目中说的闭区间，后面的比较会更加方便 bool flag=true;cnt=0; for (int i=1; i<=n; i++){ int a1,a2,a3,a4; scanf("%d:%d-%d:%d",&a1,&a2,&a3,&a4);             timeNode t1(a1,a2),t2(a3,a4);             tiInt[++cnt].startTime=t1; tiInt[cnt].endTime=t2; } sort(tiInt+1,tiInt+1+cnt,comp); for (int i=1; i<cnt; i++){//最后一个区间不合并 if(tiInt[i+1].startTime-tiInt[i].endTime<A){//两个区间之间睡眠时间少于a，区间合并                 tiInt[i].endTime=tiInt[i+1].endTime; for (int j=i+1; j<cnt; j++)//向前挪                     tiInt[j]=tiInt[j+1];                 cnt--; i--; } } if(cnt!=1 && tiInt[1].startTime-tiInt[cnt].endTime<A){             tiInt[cnt].endTime=tiInt[1].endTime; for (int i=1; i<cnt; i++) tiInt[i]=tiInt[i+1];             cnt--; } //        所有区间合并完毕，剩下的空余时间都可以用来完整睡觉。 //        输出合并结果，查看 //        for (int i=1; i<=cnt; i++){//output //            printf("OUTPUT: %02d:%02d-%02d:%02dn",tiInt[i].startTime.h,tiInt[i].startTime.minute,tiInt[i].endTime.h,tiInt[i].endTime.minute); //        } for (int i=1; i<=cnt; i++){//判断连续活动时间会不会超时 if(tiInt[i].endTime-tiInt[i].startTime>B){                 flag=false; break; } } if(!flag) { printf("Non");continue; } //        特殊情况，合并后还剩一个区间，判断剩下的时间够不够睡觉 if(cnt==1 && tiInt[1].startTime-tiInt[1].endTime<A){ printf("Non");continue; } //        剩下的时间都可以用来睡觉，直接默认睡满 printf("Yesn%dn",cnt); for (int i=1; i<=cnt; i++){             timeNode t1=plus1min(tiInt[i%cnt==0?cnt:i%cnt].endTime);             timeNode t2=minus1min(tiInt[(i+1)%cnt==0?cnt:(i+1)%cnt].startTime); printf("%02d:%02d-%02d:%02dn",t1.h,t1.minute,t2.h,t2.minute); } } return 0; }