Open xwcai98 opened 4 years ago
虽然同样使用了优先队列记录结束时间,但是优先队列其实不需要初始化,我认为以下写法更加优秀。
#include <bits/stdc++.h> using namespace std; int main() { ios::sync_with_stdio(false); cin.tie(nullptr); cout.tie(nullptr); const int st = 8 * 3600, en = 17 * 3600; int n, k; cin >> n >> k; vector<pair<int, int>> a; for (int i = 0; i < n; ++i) { string time; int op; cin >> time >> op; int t = stoi(time.substr(0, 2)) * 3600 + stoi(time.substr(3, 2)) * 60 + stoi(time.substr(6, 2)); if (t >= en) continue; a.emplace_back(t, min(op * 60, 3600)); } sort(a.begin(), a.end()); int tot = 0, now = st; priority_queue<int, vector<int>, greater<int>> q; for (auto e: a) { now = max(now, e.first); while (!q.empty() && q.top() <= now) q.pop(); if (q.size() == k) { now = max(now, q.top()); q.pop(); } q.push(now + e.second); tot += now - e.first; } int cnt = a.size(); cout << fixed << setprecision(1) << tot / 60.0 / cnt << '\n'; return 0; }
虽然同样使用了优先队列记录结束时间,但是优先队列其实不需要初始化,我认为以下写法更加优秀。