闹钟设有 \(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;
}