猫咪睡觉

问题描述

喵睡觉的时段是连续的，即一旦喵喵开始睡觉了，就不能被打扰。
可以假设喵喵必须要睡眠连续不少于 A 个小时，即一旦喵喵开始睡觉了，至少连续 A 个小时内（即 A×60 分钟内）不能被打扰！
喵不能连续活动超过 B 个小时。
喵要看新番，播放时间它已经贴在床头啦（每天都用同一张时间表），这段时间它必须醒着！！
求安排睡眠时间。

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

输出的第一行是 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

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

Limitation

Time limit      1000 ms
Memory limit    32768 kb

解题思路

太坑了太坑了太坑了！！！

时间是闭区间，比如 7:00-8:00 是 61 分钟。

每天的 timetable 都是一样的，也就是说今天这个点在干嘛明天还是在干嘛，一开始我没想到这个问题，所以每天都从 0:00 开始规划……时间是一个闭环。

所有时间统一用分钟处理，若录入的开始时间 > 结束时间，则跨天，结束时间 + 24 小时。

录入时间都排序后，需要判断进行合并区间。若间歇时间 < a 小时，则这两个时间区间需要合并。

处理完后，判断这些醒着的时间是否 > b小时。

安排睡眠时间，从 1 天的时间环中挖去这些醒着的时间，剩下的全部安排为睡眠时间。

判断安排的这些睡眠时间是否低于 a 小时。

输出统一将分钟改为 hh:mm，若超出 24 小时，则扣去。

注意 Yes/No 还是 YES/NO。

然后……WA WA WA WA WA…，我放弃了/(ㄒoㄒ)/。

源代码

#include <iostream>
#include <algorithm>
#include <vector>
#include <iomanip>
#include <queue>
using namespace std;

struct theTime {
	int begin, end;
	theTime() { begin = 0; end = 0; }
	theTime(int b, int e) :begin(b), end(e) {  }
	bool operator<(const theTime& t) {
		return begin < t.begin;
	}
};

vector<theTime> solve(int a, int b, vector<theTime> &v) {
	deque<theTime> q;
	for (int i = 0; i != v.size(); i++)
		q.push_back(v[i]);
	vector<theTime> ve;
	while (!q.empty()) {
		theTime t1 = q.front();
		q.pop_front();
		if (q.empty()) {
			ve.push_back(t1);
			break;
		}
		theTime t2 = q.front();

		if ((t2.begin - t1.end + 1) < a * 60) {
			t1.end = t2.end;
			q.pop_front();
			q.push_front(t1);
		}
		else
			ve.push_back(t1);
	}
	if (ve.size() > 1 && (ve[0].begin + 24 * 60 - ve.back().end + 1) < a * 60) {
		int newBegin = ve.back().begin;
		ve.pop_back();
		ve[0].begin = newBegin;
		ve[0].end += (24 * 60);
		sort(ve.begin(), ve.end());
	}

	bool overWake = false;
	vector<int> sT;
	for (int i = 0; i != ve.size(); i++) {
		theTime curTime = ve[i];
		if ((curTime.end - curTime.begin + 1) > b * 60) {
			overWake = true;
			break;
		}
		sT.push_back(curTime.begin - 1);
		sT.push_back(curTime.end + 1);
	}
	vector<theTime> ans;
	if (overWake || sT.empty()) {
		ans.clear();
		return ans;
	}
	int ta = sT.back();
	int tb = sT[0] + 24 * 60;
	if (tb - ta + 1 < a * 60) {
		ans.clear();
		return ans;
	}
	else {
		theTime ax(ta, tb);
		ans.push_back(ax);
	}
	for (int i = 1; i != sT.size() - 1; i++) {
		int ta = sT[i];
		i++;
		int tb = sT[i];
		if ((tb - ta) < a * 60) {
			ans.clear();
			break;
		}
		else {
			theTime ax(ta, tb);
			ans.push_back(ax);
		}
	}
	return ans;
}

void outTime(int t) {
	int m = t % 60;
	int h = t / 60;
	if (h >= 24)
		h -= 24;
	cout << setw(2) << setfill('0') << h << ":";
	cout << setw(2) << setfill('0') << m;
}

int main() {
	int a, b, n;
	while (!(cin >> a >> b >> n).eof()) {
		vector<theTime> v;
		for (int i = 0; i < n; i++) {
			int h1, m1, h2, m2;
			char temp;
			cin >> h1 >> temp >> m1 >> temp >> h2 >> temp >> m2;
			int t1 = h1 * 60 + m1;
			int t2 = h2 * 60 + m2;
			if (t2 < t1)
				t2 += (24 * 60);
			theTime tt(t1, t2);
			v.push_back(tt);
		}
		sort(v.begin(), v.end());
		vector<theTime> v1 = solve(a, b, v);
		if (v1.empty())
			cout << "No" << endl;
		else {
			cout << "Yes" << endl;
			cout << v1.size() << endl;
			for (int i = 0; i != v1.size(); i++) {
				outTime(v1[i].begin);
				cout << "-";
				outTime(v1[i].end);
				cout << endl;
			}
		}
	}
	return 0;
}