猫睡觉问题

题目描述

众所周知，TT家里有一只魔法喵。这只喵十分嗜睡。一睡就没有白天黑夜。喵喵一天可以睡多次！！每次想睡多久就睡多久╭(╯^╰)╮

喵睡觉的时段是连续的，即一旦喵喵开始睡觉了，就不能被打扰，不然喵会咬人哒[○･｀Д´･ ○]

可以假设喵喵必须要睡眠连续不少于 A 个小时，即一旦喵喵开始睡觉了，至少连续 A 个小时内（即A*60分钟内）不能被打扰！

现在你知道喵喵很嗜睡了，它一天的时长都在吃、喝、拉、撒、睡，换句话说要么睡要么醒着滴！

众所周知，这只魔法喵很懒，和TT一样懒，它不能连续活动超过 B 个小时。

猫主子是不用工作不用写代码滴，十分舒适，所以，它是想睡就睡滴。

但是，现在猫主子有一件感兴趣的事，就是上BiliBili网站看的新番。

新番的播放时间它已经贴在床头啦（每天都用同一张时间表哦），这段时间它必须醒着！！

作为一只喵喵，它认为安排时间是很麻烦的事情，现在请你帮它安排睡觉的时间段。
https://vjudge.net/contest/375063#problem/A

题意分析

大体思路如下：
遍历整个时间表，如果空闲时间大于等于猫的最低睡眠时间，那么这段时间可以睡觉，否则这段时间也在视为看番剧，即将后一个番剧的开始时间更新为当前番剧的开始时间。
除了思路之外还有注意以下几点：
（1）首先，答案不唯一，我们输出睡觉最多的一种就可
（2）本题的难点之一是要注意有跨夜的新番，对于第二天的时间同一加上24做到时间的标准化
（3）注意时间差的计算，12:00 - 13:00是61min
（4）注意猫一定要睡觉，不能持续活动

通过代码

#include<iostream>
#include<algorithm>
#include<vector>
#include<cstring>
#include<string>
#include<queue>
#include<cstdlib>
#include<sstream>
#include<cmath>
#define inf 0x3f3f3f3f
using namespace std;
int turnh(string s){
    string th="aa";
    string ts="aa";
    th=s.substr(0,2);
    ts=s.substr(3,2);
    return atoi(th.c_str())*60+atoi(ts.c_str());
}
struct timeStage{
    int be,en;
}ts[30];
timeStage tmp;
bool cmp(timeStage& a, timeStage& b){
    return a.be<b.be;
}
const int offset = 24*60;
int a,b,n;
string time;
int be,en;

bool flag;
vector<timeStage> ans;
int main(){
    std::ios::sync_with_stdio(false);
    while(cin>>a>>b>>n){
        ans.clear();
        flag=false;
        a*=60;
        b*=60;
        for(int i=0;i<n;i++){
            cin>>time;
            
            ts[i].be=turnh(time.substr(0,5));
            
            ts[i].en=turnh(time.substr(6,5));
            
            if(ts[i].be>ts[i].en)ts[i].en+=offset;
        }
        sort(ts,ts+n,cmp);
        for (int i=0; i<n; i++)
        {
            if (ts[i].en-ts[i].be+1>b)
            {
                flag = true;
                break;
            }
        }
        //tmp=ts[0];
        //cout<<tmp.en<<"sz"<<endl;
        timeStage tmp2;
        if(!flag){
            //cout<<"dsds";
            tmp=ts[0];
          // cout<<tmp.be<<' '<<tmp.en<<endl;
          // cout<<ts[1].be<<endl;
        for(int i=1;i<n;i++){
            //if(ts[i].en-ts[i].be+1>b) {flag=true;break;}
            if(ts[i].be-tmp.en-1>=a){
                //cout<<"dsds"<<endl;
                tmp2.be=tmp.en+1;
                tmp2.en=ts[i].be-1;
                //cout<<tmp2.be<<' '<<tmp2.en<<endl;
                if(tmp2.be!=tmp2.en)
                    ans.push_back(tmp2);
                tmp.be=ts[i].be;
                tmp.en=ts[i].en;

            }
            else{
                tmp.en=ts[i].en;
                if(tmp.en-tmp.be+1>b) {flag=true;break;}
            }
        }
    }
        //cout<<ans.size()<<"sz"<<endl;
        if(!flag){
            if(ts[0].be+offset-tmp.en-1>=a){
                tmp2.be=(tmp.en+1)%offset;
                tmp2.en=(ts[0].be+offset-1)%offset;
                if(tmp2.be!=tmp2.en) ans.push_back(tmp2);
            }
            else if((ans[1].be-1+offset)%offset-tmp.be+1>b) flag=true;
            if(ans.size() && (!flag)){
                cout<<"Yes\n"<<ans.size()<<endl;
                sort(ans.begin(), ans.end(), cmp);
                for(int i=0;i<ans.size();i++){
                    cout<<ans[i].be/600<<ans[i].be/60%10<<":"<<ans[i].be%60/10<<ans[i].be%10<<"-"<<ans[i].en/600<<ans[i].en/60%10<<":"<<ans[i].en%60/10<<ans[i].en%10<<endl;

                }
            }
            else cout<<"No\n";
        }
        else cout<<"No\n";

    }   
}