CF1714A Everyone Loves to Sleep 题解

· · 题解

本题考察入门的选择结构与循环结构。

很显然，我们需要找出离 Vlad 睡觉时响得最早的那个闹钟。

这是我们就需要分类讨论：

设 H,M 是他上床睡觉的时间，h_i,m_i 是第 i 个闹钟响的时间，那么：

如果 H=h_i，那么就比较 M 和 m_i，如果 M\le m_i，那么他就可以睡 23:(M-m_i)；否则他可以睡 0:60-(M-m_i)；

如果 H<h_i，那么类似的，如果 M\le m_i，那么他就可以睡 (H-h_i):(M-m_i)；否则他可以睡 (H-h_i-1):60-(M-m_i)；

如果 H>h_i，就是说他到第二天才能醒，那么如果 M\le m_i，那么他就可以睡 24-(H-h_i):(M-m_i)；否则他可以睡 24-(H-h_i)-1:60-(M-m_i)；

最后将所有的时间插入小根堆，取出堆顶就是答案。

放代码：

#include<bits/stdc++.h>
using namespace std;
typedef pair<int,int> pii;
pii d(int h1,int m1,int h2,int m2){
  if(h1==h2)return make_pair(m1<m2?23:0,m1>m2?m1-m2:(60+m1-m2)%60);
  if(h1>h2)return make_pair(h1-h2-(m1<m2),m1>m2?m1-m2:(60+m1-m2)%60);
  return make_pair(24+h1-h2-(m1<m2),m1>m2?m1-m2:(60+m1-m2)%60);
}
int main(){
  ios::sync_with_stdio(false);
  int t; cin>>t;
  while(t--){
    int n,h0,m0; cin>>n>>h0>>m0;
    vector<pii> a(n);
    priority_queue<pii,vector<pii>,greater<> > q;
    for(auto &[h,m]:a)cin>>h>>m,q.push(d(h,m,h0,m0));
    cout<<q.top().first<<' '<<q.top().second<<endl;
  }
  return 0;
}