UVa 480 Tempus Fugit

题目描述

某企业老板工作时间为周一至周五，每天9:009 : 009:00至17:0017 : 0017:00，午餐时段为12:3012 : 3012:30至13:3013 : 3013:30。她要求所有预约至少提前两周提出，并按提出顺序依次处理（先到先得）。您的程序需要为接下来的一个工作周安排预约。

预约时间必须以101010分钟为粒度（开始时刻为整点、101010分、202020分、303030分、404040分或505050分）。若请求的开始或结束时间不在这些分界点上，则将其调整到包含它的两个101010分钟分界点之间（开始向下取整，结束向上取整）。每个已安排的预约之后需要插入101010分钟休息时间，除非该预约结束于12:3012 : 3012:30或17:0017 : 0017:00。预约不能跨越午餐时段，也不能开始于午餐时段内。每天安排的总时长（调整后的时长，不含休息）不得超过444小时（240240240分钟）。

若某个预约无法在其请求的日期安排，则依次尝试当周后续的每一天（同一时刻），安排到第一个可行的日子。若所有尝试均失败，则将该请求者姓名加入“无法安排”列表。

输入格式

输入文件最多包含252525个预约请求，每行一个，格式如下：

name day start_hour start_minute duration_hour duration_minute

其中name占前101010个字符位置，由字母数字组成；day为MON、TUE、WED、THU或FRI；start_hour和start_minute表示开始时间（121212小时制）；duration_hour和duration_minute表示持续时间。例如：

Johnstone TUE 09 15 1 30

表示Johnstone\texttt{Johnstone}Johnstone请求周二9:159 : 159:15开始、时长111小时303030分钟的预约。

输入数据保证所有字段合法，且时间以最大小时数表示（如909090分钟会写为1 30，不会写为0 90）。

输出格式

输出分为两部分：

1. 本周的日程表，按周一至周五顺序输出。每一天先输出日期（如MONDAY），然后按时间升序列出该日的所有预约，每个预约格式为姓名 起始时间 to 结束时间，时间采用121212小时制（如9:00、2:30）。若该日无预约，则输出No Appointments Scheduled。
2. 最后输出APPOINTMENTS COULD NOT BE SCHEDULED FOR:，随后每行一个无法安排的人员姓名。

样例

输入

Johnstone TUE 09 15 1 30 Peterson MON 09 00 0 30 McKeever FRI 09 30 1 00 Garzarelli THU 10 45 0 20 Tucker MON 10 00 2 30 Davis MON 02 30 1 00 Corrigan MON 02 00 0 15 Trump WED 01 00 3 00 Logan THU 09 45 1 05 Schulman THU 11 10 0 30

输出

APPOINTMENT SCHEDULE FOR THE WEEK MONDAY Peterson 9:00 to 9:30 Tucker 10:00 to 12:30 Davis 2:30 to 3:30 TUESDAY Johnstone 9:10 to 10:50 Corrigan 2:00 to 2:20 WEDNESDAY No Appointments Scheduled THURSDAY Garzarelli 10:40 to 11:10 FRIDAY McKeever 9:30 to 10:30 Schulman 11:10 to 11:40 APPOINTMENTS COULD NOT BE SCHEDULED FOR: Trump Logan

题目分析

本题是一道模拟预约调度的问题，关键点在于：

• 时间的表示与调整：输入采用121212小时制（如02 30表示下午2:302 : 302:30），需转换为242424小时制分钟数。预约的起止时间需按101010分钟粒度调整（开始向下取整，结束向上取整），调整后的时长用于444小时限制。
• 日程的约束条件：每天工作时段为9:00–17:009 : 00 – 17 : 009:00–17:00，午餐时段12:30–13:3012 : 30 – 13 : 3012:30–13:30不可用。预约不能跨午餐，也不能在午餐期间开始。每个预约后需插入101010分钟休息（除非结束于12:3012 : 3012:30或17:0017 : 0017:00），因此休息块也需要检查空闲。
• 预约的优先级与重试机制：按输入顺序处理，先到先得。若指定日期无法安排，则尝试同一天该周后续的日子，不尝试更早的日子，也不尝试不同时刻。这一重试机制使得即使某天已满，预约仍可能在后续日期成功。
• 每日总时长限制：每天所有调整后的预约时长之和不得超过240240240分钟。注意，444小时限制仅针对调整后的时长，不包含休息时间。

由于输入规模很小（最多252525个请求），我们无需高级数据结构，直接模拟即可。关键在于正确处理所有时间转换和边界条件。

解题思路

时间转换与块划分

将一天的工作时间（9:00–17:009 : 00 – 17 : 009:00–17:00）划分为484848个101010分钟块，用布尔数组occupied[day][block]标记每个块是否已被占用。午餐时段（12:30–13:3012 : 30 – 13 : 3012:30–13:30）对应的块（从212121到262626，共666个块）初始即标记为已占用。

输入的小时数采用121212小时制：若小时数小于999（例如02代表下午222点），则加上121212转换为242424小时制。这样得到起始分钟startOrig = sh * 60 + sm，结束分钟endOrig = startOrig + dh * 60 + dm。然后进行101010分钟取整：

• 起始调整：startAdj = floor10(startOrig)，即向下取整到最近的101010分钟分界点。
• 结束调整：endAdj = ceil10(endOrig)，即向上取整到最近的101010分钟分界点。
  调整后的时长adjDur = endAdj - startAdj，用于累加每日总时长。

安排条件的检查

对于某一天ddd，判断能否安排一个调整后的预约区间[startAdj, endAdj)需满足以下条件：

1. 预约区间必须在工作时段内（9:00 ≤ startAdj < endAdj ≤ 17:00）。
2. 不能跨越午餐时段：即不能出现startAdj < LUNCH_START且endAdj > LUNCH_START的情况；也不能在午餐时段内开始（startAdj不能在[LUNCH_START, LUNCH_END)内）。
3. 区间内所有101010分钟块均空闲。
4. 当日累计调整时长 +adjDur≤240240240分钟。
5. 如果需要添加休息（即endAdj ≠ 12:30且endAdj ≠ 17:00），则紧随其后的那个101010分钟块也必须空闲，且该休息块不能跨越午餐（但若endAdj合法，该块结束时间不会进入午餐，因为休息块从endAdj开始，其结束为endAdj + 10，若endAdj为12:2012 : 2012:20，休息至12:3012 : 3012:30恰好合法；若endAdj为16:5016 : 5016:50，休息至17:0017 : 0017:00也合法，均符合规则）。

上述条件全部满足后，执行安排：将预约占用的块标记为已占用，累加当日总时长，记录预约信息；若需要休息，同时将休息块标记为已占用。

重试机制

对于每个请求，从指定的日期开始，依次尝试当天及后续的每一天（直到周五），一旦在某天成功，则不再尝试更晚的日子。若所有天数均失败，则将该请求者姓名加入failed列表。

输出处理

每天按起始时间升序输出该日的预约。时间格式化为121212小时制：若小时数≥13≥ 13≥13，则减去121212得到下午的显示小时；分钟不足两位时补零。注意输出格式中，样例中日期行和预约行均无多余缩进，而“无预约”的行也不带缩进，最终我们采用与样例一致的无前导空格输出。

代码实现

// Tempus Fugit// UVa ID: 480// Verdict: Accepted// Submission Date: 2026-06-27// UVa Run Time: 0.000s//// 版权所有（C）2026，邱秋。metaphysis # yeah dot net#include<bits/stdc++.h>usingnamespacestd;constintWORK_START=9*60;constintWORK_END=17*60;constintLUNCH_START=12*60+30;constintLUNCH_END=13*60+30;constintBLOCK=10;constintMAX_DAILY=240;constintDAYS=5;constintBLOCKS_PER_DAY=(WORK_END-WORK_START)/BLOCK;intdayIndex(conststring&d){if(d=="MON")return0;if(d=="TUE")return1;if(d=="WED")return2;if(d=="THU")return3;return4;}stringdayName(inti){staticconststring names[DAYS]={"MONDAY","TUESDAY","WEDNESDAY","THURSDAY","FRIDAY"};returnnames[i];}stringformatTime(intminutes){inth=minutes/60,m=minutes%60;if(h>=13)h-=12;string hh=to_string(h);string mm=(m<10?"0":"")+to_string(m);returnhh+":"+mm;}intfloor10(intt){return(t/BLOCK)*BLOCK;}intceil10(intt){return((t+BLOCK-1)/BLOCK)*BLOCK;}structAppointment{string name;intstartMin,endMin;};booloccupied[DAYS][BLOCKS_PER_DAY];intdailyTotal[DAYS];vector<Appointment>schedule[DAYS];vector<string>failed;boolisFree(intday,intblock){return!occupied[day][block];}boolcanPlace(intday,intstartMin,intendMin,intdur){if(startMin<WORK_START||endMin>WORK_END||startMin>=endMin)returnfalse;if(startMin<LUNCH_START&&endMin>LUNCH_START)returnfalse;if(startMin>=LUNCH_START&&startMin<LUNCH_END)returnfalse;intstartBlock=(startMin-WORK_START)/BLOCK;intendBlock=(endMin-WORK_START)/BLOCK;for(intb=startBlock;b<endBlock;++b)if(!isFree(day,b))returnfalse;if(dailyTotal[day]+dur>MAX_DAILY)returnfalse;returntrue;}voidplaceAppointment(intday,conststring&name,intstartMin,intendMin){intdur=endMin-startMin;intstartBlock=(startMin-WORK_START)/BLOCK;intendBlock=(endMin-WORK_START)/BLOCK;for(intb=startBlock;b<endBlock;++b)occupied[day][b]=true;dailyTotal[day]+=dur;schedule[day].push_back({name,startMin,endMin});if(endMin!=LUNCH_START&&endMin!=WORK_END){intbreakBlock=(endMin-WORK_START)/BLOCK;occupied[day][breakBlock]=true;}}intmain(){ios::sync_with_stdio(false);cin.tie(nullptr);for(intd=0;d<DAYS;++d){for(intb=0;b<BLOCKS_PER_DAY;++b)occupied[d][b]=false;intlunchStartBlock=(LUNCH_START-WORK_START)/BLOCK;intlunchEndBlock=(LUNCH_END-WORK_START)/BLOCK;for(intb=lunchStartBlock;b<lunchEndBlock;++b)occupied[d][b]=true;dailyTotal[d]=0;}string name,day;intsh,sm,dh,dm;vector<tuple<string,int,int,int>>requests;while(cin>>name>>day>>sh>>sm>>dh>>dm){if(sh<9)sh+=12;// 将下午时间转换为24小时制intstartOrig=sh*60+sm;intdur=dh*60+dm;intdayIdx=dayIndex(day);requests.emplace_back(name,startOrig,dur,dayIdx);}for(auto&req:requests){string reqName=get<0>(req);intstartOrig=get<1>(req);intdur=get<2>(req);intreqDay=get<3>(req);intstartAdj=floor10(startOrig);intendAdj=ceil10(startOrig+dur);intadjDur=endAdj-startAdj;boolscheduled=false;for(intd=reqDay;d<DAYS;++d){if(!canPlace(d,startAdj,endAdj,adjDur))continue;boolneedBreak=(endAdj!=LUNCH_START&&endAdj!=WORK_END);if(needBreak){intbreakBlock=(endAdj-WORK_START)/BLOCK;if(breakBlock<0||breakBlock>=BLOCKS_PER_DAY)continue;if(!isFree(d,breakBlock))continue;}placeAppointment(d,reqName,startAdj,endAdj);scheduled=true;break;}if(!scheduled)failed.push_back(reqName);}cout<<"APPOINTMENT SCHEDULE FOR THE WEEK\n";for(intd=0;d<DAYS;++d){cout<<dayName(d)<<"\n";if(schedule[d].empty()){cout<<"No Appointments Scheduled\n";}else{sort(schedule[d].begin(),schedule[d].end(),[](constAppointment&a,constAppointment&b){returna.startMin<b.startMin;});for(constauto&app:schedule[d])cout<<app.name<<" "<<formatTime(app.startMin)<<" to "<<formatTime(app.endMin)<<"\n";}}cout<<"APPOINTMENTS COULD NOT BE SCHEDULED FOR:\n";for(conststring&s:failed)cout<<s<<"\n";return0;}

总结

本题模拟预约调度，核心难点在于：

• 时间处理：正确转换121212小时制到242424小时制，并严格按照101010分钟粒度调整起止时间。
• 约束检查：同时考虑空闲块、午餐时段、每日444小时限制以及休息块的插入，缺一不可。
• 重试逻辑：按输入顺序处理，并仅向当周后续日期尝试，符合题目要求。

由于数据规模很小，使用简单的数组模拟即可高效解决。编写此类模拟题时，应仔细阅读题目描述的每一条规则，并通过样例测试验证边界情况（如午餐边界、休息块插入条件、时间格式等），确保所有细节无误。本题通过率较高的关键在于对121212小时制的正确转换（下午111点至555点对应小时数13–1713 – 1713–17），以及休息块检查的完备性。