526互联

Codeforces Round 811 (Div. 3) A. Everyone Loves to Sleep

发布时间 2023-09-10 19:00:58作者: zsxuan

闹钟设有 \(n\) 个时间点，第 \(i\) 个时间为 \((H_i,M_i)\) 。在 \(h, m\) 时刻入睡，响铃必须起床，问能睡多久。

使用 \(set<pair<int, int>>\) 存储闹铃时刻，然后在其中 \(lower_{bound}\) 到 \(<first \geq h, second \geq m>\) 的迭代器 \(it\) 。

若 \(it = end\) ，则 \(it = begin\) ，根据环链关系 \(first += 24\) 。

于是 \(h = it->first, m = it->second\) 。 \(m\) 可能为负，调整即得到答案。

时间复杂度 \(O(n \log n)\) 。

view 
#include <bits/stdc++.h>
long long gcd(long long a, long long b) {return b?gcd(b,a%b):a;}
void solve() {
	int n; std::cin >> n;
	int h, m; std::cin >> h >> m;
	std::set<std::pair<int, int>> px;
	for (int i = 1, x,y; i <= n; i++) {std::cin >> x >> y; px.insert({x, y}); };
	auto R = px.lower_bound({h, m});
	int nxth = 0, nxtm = 0;
	if (R == px.end()) R = px.begin(), nxth += 24;
	nxth += R->first, nxtm += R->second;
	h = nxth - h; m = nxtm - m;
	if (m < 0) m += 60, h -= 1;
	std::cout << h << ' ' << m << '\n';
}
signed main() {
	int _ = 1; std::cin >> _;
	while (_--) solve();
	return 0;
}