算法
模拟
题目描述
给出一个时间表，在时间表内猫只能醒着；
给出猫一次最短睡眠时间和一次最长清醒时间，找出是否满足要求，并安排猫的睡觉时间。
解题思路
由于一天只有24小时，每小时60分钟，使用数组存储并计算每一分钟完全可行。
先将所有时间表内时间标记，再将所有不能睡觉的时间标记（间隔较小的时间），之后查询是否满足，如果满足，按照此输出即可
代码
#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;
int fan[24][60];
int slp[24][60];
void kanfan(int sth, int stm, int ndh, int ndm) {
int st = sth * 60 + stm, nd = ndh * 60 + ndm;
if (nd < st) {
nd += 60 * 24;
}
for (int i = st; i <= nd; i++) {
int h = (i / 60) % 24;
int m = (i % 60);
fan[h][m] = 1;
}
return;
}
int maxshui(int ss) {
int rtn = 0;
int cnt = 0;
int beg = 0;
for (int h = 0; h < 24; h++) {
for (int m = 0; m < 60; m++) {
if (fan[h][m] == 1) {
if ((cnt < ss)&&cnt!=0) {
int nd = h * 60 + m;
for (int i = nd-1; i >= 0; i--) {
int hh = (i / 60) % 24;
int mm = (i % 60);
if (fan[hh][mm] == 1) {
break;
}
else {
fan[hh][mm] = 1;
}
}
}
rtn = max(rtn, cnt);
cnt = 0;
beg = 1;
}
else {
if(beg) cnt++;
}
}
}
cnt = 0;
int ok = 0;
for (int h = 0; h < 24; h++) {
if (ok) break;
for (int m = 0; m < 60; m++) {
if (fan[h][m] == 1) {
ok = 1;
break;
}
else {
cnt++;
}
}
}
ok = 0;
for (int h = 23; h >= 0; h--) {
if (ok) break;
for (int m = 59; m >= 0; m--) {
if (fan[h][m] == 1) {
ok = 1;
break;
}
else {
cnt++;
}
}
}
rtn = max(rtn, cnt);
if (cnt < ss) {
int ok = 0;
for (int h = 0; h < 24; h++) {
if (ok) break;
for (int m = 0; m < 60; m++) {
if (fan[h][m] == 1) {
ok = 1;
break;
}
else {
fan[h][m] = 1;
}
}
}
ok = 0;
for (int h = 23; h >= 0; h--) {
if (ok) break;
for (int m = 59; m >= 0; m--) {
if (fan[h][m] == 1) {
ok = 1;
break;
}
else {
fan[h][m] = 1;
}
}
}
}
return rtn;
}
int maxxing() {
int rtn = 0;
int cnt = 0;
for (int h = 0; h < 24; h++) {
for (int m = 0; m < 60; m++) {
if (fan[h][m] == 0) {
rtn = max(rtn, cnt);
cnt = 0;
}
else {
cnt++;
}
}
}
cnt = 0;
int ok = 0;
for (int h = 0; h < 24; h++) {
if (ok) break;
for (int m = 0; m < 60; m++) {
if (fan[h][m] == 0) {
ok = 1;
break;
}
else {
cnt++;
}
}
}
ok = 0;
for (int h = 23; h >= 0; h--) {
if (ok) break;
for (int m = 59; m >= 0; m--) {
if (fan[h][m] == 0) {
ok = 1;
break;
}
else {
cnt++;
}
}
}
rtn = max(rtn, cnt);
if (rtn == 2880)
rtn = 1440;
return rtn;
}
int main() {
//freopen("A.txt","w",stdout);
int shui, xing, n;
while (cin >> shui >> xing >> n) {
memset(fan, 0, sizeof(fan));
memset(slp, 0, sizeof(slp));
for (int i = 1; i <= n; i++) {
int sth, stm, ndh, ndm;
scanf("%d:%d-%d:%d", &sth, &stm, &ndh, &ndm);
kanfan(sth, stm, ndh, ndm);
}
int maxs = maxshui(shui*60);
int maxx = maxxing();
if (xing*60 < maxx) {
cout << "No" << endl;
}
else {
if (xing == 24) {
int ok = 0;
for (int i = 1; i < 1440; i++) {
int h = (i / 60) % 24;
int m = (i % 60);
if (fan[h][m] == 0) {
ok = 1;
break;
}
}
if(!ok){
cout << "No" << endl;
continue;
}
}
cout << "Yes" << endl;
int beg = 0;
int cnt = 0;
for (int h = 0; h < 24; h++) {
for (int m = 0; m < 60; m++) {
if (fan[h][m] == 1) {
if (beg) {
cnt++;
}
beg = 0;
}
else {
beg = 1;
}
}
}
if (fan[0][0] == 1 && fan[23][59] == 0)cnt++;
cout << cnt << endl;
int cntu = 0;
int prt = 0;
beg = 1;
bool frt = 1;
for (int h = 0; h < 24; h++) {
for (int m = 0; m < 60; m++) {
if (fan[h][m] == 1) {
if (beg && (!frt)) {
int hh = h;
int mm = m - 1;
if (mm < 0) {
mm = 59;
hh--;
}
printf("%02d:%02d\n", hh, mm);
cntu++;
}
beg = 0;
frt = 0;
}
else {
if (!beg && (!frt)) {
printf("%02d:%02d-", h, m);
prt++;
}
beg = 1;
}
}
}
if (cnt == cntu) continue;
if (prt < cnt) {
printf("00:00-");
}
int ok = 0;
for (int h = 0; h < 24; h++) {
if (ok) break;
for (int m = 0; m < 60; m++) {
if (fan[h][m] == 1) {
ok = 1;
int hh = h;
int mm = m - 1;
if (mm < 0) {
mm = 59;
hh--;
hh += 24;
hh %= 24;
}
printf("%02d:%02d\n", hh, mm);
cntu++;
break;
}
}
}
if (cntu < cnt) {
printf("23:59");
}
}
}
return 0;
}
/*
12 12 1
23:00-01:00
3 4 3
07:00-08:00
11:00-11:09
19:00-19:59
3 4 3
07:00-08:00
11:08-11:09
19:00-19:59
8 24 3
07:00-08:00
11:08-11:09
19:00-06:59
3 4 3
07:00-08:00
22:08-23:09
02:09-03:09
1 23 1
02:00-00:59
2 4 3
19:00-21:00
22:00-22:59
01:00-03:00
4 2 2
16:00-16:59
00:00-01:00
4 10 5
02:17-03:05
08:18-09:12
14:15-16:02
19:52-22:40
23:15-01:59
1 3 6
00:00-02:00
03:01-04:59
08:00-10:00
11:10-13:00
15:00-17:00
23:30-23:40
1 12 5
00:00-01:00
03:00-05:00
07:00-09:00
10:00-13:00
15:00-23:00
3 3 5
01:00-02:00
09:00-10:00
03:00-05:00
11:00-20:00
21:00-00:59
3 24 3
08:00-12:00
15:00-15:30
16:00-06:30
3 7 3
4:00-5:00
00:00-2:59
10:00-11:00
2 24 2
00:00-10:00
12:00-23:59
2 7 3
00:00-01:00
02:00-06:59
10:00-12:00
*/
题目总结
模拟题一定要先明确思路，并且要注意特殊情况的判断；如猫猫如果可以24小时清醒，那么时间上并不能在24小时内全都醒着，因为并非针对一天来说。。
题目原文
众所周知，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
你尝试给喵喵喂小鱼干，它告诉了你一个秘密：“媌，吧唧吧唧小鱼…吧唧吧唧干香吧唧吧唧，媌，这题最麻烦吧唧吧唧…的吧唧吧唧是最后一个番到第二天第一个番期间时间段的处理哦，媌，但是吧唧吧唧可以有一种方法可以很容易处理吧唧吧唧吧唧。啊呀，我要去睡觉啦，媌”
解题思路
实现代码
