SDU程序设计思维Week14 模拟题-Cat

Description

Sample

Input:
12 12 1
23:00-01:00
3 4 3
07:00-08:00
11:00-11:09
19:00-19:59
Output:
Yes
1
01:07-22:13
No

Idea

• fan结构体表示一段时间，包含开始时间start和结束时间end
• 获取新番的时间表，将字符串转化成整数
  如果某个新番的时段横跨两天（开始时间大于结束时间），则将结束时间加上一天代表第二天的这个时间。
  将新番时间表排序，并检查有没有单个新番的时间段就已经大于b，如果有，已经不符合要求跳过之后的操作。
• 寻找不少于a小时的时间段用于睡觉
  遍历每两个新番之间的空闲时间，将空闲时间不少于a的时间段记录下来。
  如果空闲时间少于a，则检查前一个新番的起始时间到后一个新番的结束时间这个时间段是否满足不超过b，如果超过则已不符合要求。
  单独考虑最后一个新番的时间即两天交界的时间段，如果最后一个新番的结束时间至第二天第一个新番的开始时间满足睡觉的要求，则记录为睡觉时间，若不满足睡觉要求，则检查最后一个新番的开始时间至第二天第一次睡觉的开始时间这段时间段是否满足不超过b
• 最后如果有符合要求的睡觉时间段则将整数转换成字符串输出

Summary

这题是复杂的模拟题，可以确定策略就是检查两个新番间的空闲时间是否可以成为睡觉时间。难点在于两天交界的那段时间，如果这段时间没有新番，则检查是否可以成为睡觉时间；如果有新番，则检查醒着的时间是否超过b，要注意这里是最后一个新番的开始时间到第二天第一次睡觉的开始时间，而不是最后一个新番的开始到它的结束。
另外注意时间段是闭区间的问题，以及输出Yes而不是YES(WA了好几发)…

Codes

#include <iostream>
#include <string>
#include <algorithm>
#include <vector>
using namespace std;

struct fan {
	int start;
	int end;
	fan(){}
	fan(int s, int e) {
		start = s, end = e;
	}
	bool operator<(fan& x)const {
		return start < x.start;
	}

}f[25];

int a,b,n,k;


void pprint(vector<fan> x) {
	int m = x.size();
	for (int i = 0; i < m; i++) {
		printf("%d%d:%d%d-%d%d:%d%d\n", x[i].start / 600, x[i].start / 60 % 10, x[i].start % 60 / 10, x[i].start % 10, x[i].end / 600, x[i].end / 60 % 10, x[i].end % 60 / 10, x[i].end % 10);
	}

}


int main()
{
	//while (cin >> a >> b >> n)
	while(scanf("%d%d%d",&a,&b,&n)!=EOF)
	{
		
		
		bool flag = true;
		
		for (int i = 1; i <= n; i++)
		{
			string str;
			cin >> str;
			f[i].start = (str[0] - '0') * 600 + (str[1] - '0') * 60 + (str[3] - '0') * 10 + (str[4] - '0');
			f[i].end = (str[6] - '0') * 600 + (str[7] - '0') * 60 + (str[9] - '0') * 10 + (str[10] - '0');
			if (f[i].end < f[i].start) f[i].end += 24*60;


		}

		vector<fan> slp;
		sort(f + 1, f + 1 + n);
		for (int i = 1; i <= n; i++)
		{
			if (f[i].end - f[i].start + 1 > b*60)
			{
				flag = false;
				break;
			}
		}

		fan temp,x;
		
		if (flag) {
			temp.start = f[1].start;
			temp.end = f[1].end;
			for (int i = 1; i < n; i++) {
				if (f[i + 1].start - 1 - temp.end >= a * 60)
				{
					x.start = temp.end + 1;
					x.end = f[i + 1].start - 1;
					if (x.start != x.end)slp.push_back(x);
					temp.start = f[i + 1].start;
					temp.end = f[i + 1].end;
				}
				else {
					temp.end = f[i + 1].end;
					if (temp.end - temp.start + 1 > b * 60)
					{
						flag = false;
						break;
					}
				}
			}
		}
		if (flag) {
			if (f[1].start + 24 * 60 - 1 - temp.end >= a * 60)
			{
				x.start = (temp.end + 1) % (24 * 60);
				x.end = (f[1].start - 1 + 24 * 60) % (24 * 60);
				if (x.start != x.end)slp.push_back(x);
			}
			else if (slp.empty()||(slp[1].start - 1 + 24 * 60) % 1440 - temp.start + 1 > b * 60) {
				flag = false;

			}
		}
		if (!flag||slp.empty()) {
			cout << "No" << endl;

		}
		else {
			cout << "Yes" << endl;
			cout << slp.size() << endl;
			pprint(slp);
		}


	}

}