【题目来源】学而思编程食堂排队【题目描述】某班有n nn个学生编号1 ∼ n 1\sim n1∼n。中午下课后学生们陆续赶到食堂吃饭。食堂只有一个打饭窗口所以学生们要排队打饭。第i ii个学生在第l i l_ili​分钟开始排队当然是排在队尾。如果同一分钟有多个学生同时开始排队则编号较小的学生排在编号较大的学生之前。当一名学生排在队伍的最前端时即轮到该名学生打饭。每个学生打饭需要花费一分钟时间。打到饭的学生立即离开队伍没打到饭的学生在队伍里继续等待。每个学生的耐心都是有限的。对于第i ii个学生如果在第r i r_iri​分钟时他仍在排队且未轮到他打饭仍有人排在他之前那么他就会直接离开放弃打饭。对于每个学生请你确定他是在第几分钟开始打饭即排到队首的【输入】第一行包含整数T TT表示共有T TT组测试数据。每组数据第一行包含整数n nn。接下来n nn行每行包含两个整数l i , r i l_i,r_ili​,ri​表示第i ii个学生到达队伍的时间以及忍耐的极限时间。保证同一组数据的l i l_ili​是非递减的。【输出】每组数据输出一行结果包含n nn个整数其中第i ii个整数表示第i ii个学生开始打饭的时间如果这个学生直接离开放弃打饭则输出0 00。【输入样例】2 2 1 3 1 4 3 1 5 1 1 2 3【输出样例】1 2 1 0 2【核心思想】问题分析给定n nn个学生每个学生有到达时间l i l_ili​和忍耐极限r i r_iri​。学生按到达时间排队同分钟按编号打饭需1 11分钟。若到r i r_iri​分钟仍未轮到自己则离开。求每个学生开始打饭的时间或0 00离开。这是一个贪心调度 区间覆盖问题关键在于维护当前已分配的最大时间为每个学生在其可用区间内分配最早的空闲时间。算法选择贪心分配维护当前已使用的最大时间x为每个学生分配满足条件的最小时间区间判断每个学生的可用区间为[ l i , r i ] [l_i, r_i][li​,ri​]若x落在该区间内则分配x否则调整关键步骤初始化读取T TT测试组数处理每组数据读取n nnx 0当前已分配的最大时间初始为0 00表示尚未开始遍历n nn个学生读取l i l_ili​和r i r_iri​若x l_i输出l_i该学生在其到达时即可打饭x l_i 1更新已分配最大时间否则若x r_i输出0该学生忍耐时间已过无法打饭否则l_i x r_i输出x该学生在当前最早可用时间打饭x已分配最大时间推进1 11分钟输出换行时间/空间复杂度时间复杂度O ( T × n ) O(T \times n)O(T×n)每组数据线性处理空间复杂度O ( 1 ) O(1)O(1)仅需常数变量贪心调度的核心思想最早可用时间原则为每个学生分配不早于其到达时间、不晚于其忍耐时间的最早空闲时间保证后续学生有最大可用空间时间线维护x维护当前时间线的最右端表示下一个可用时间点。若x l_i说明有空档从l_i开始若x r_i说明该学生已错过否则x恰好可用非递减到达的利用题目保证l i l_ili​非递减因此按顺序处理即可无需排序或优先队列打饭时间的连续性每个打饭操作占用1 11分钟x的递增模拟了时间的线性推进适用于区间调度 贪心分配类问题维护当前时间线即可实现最优分配【解题思路】【算法标签】#模拟【代码详解】#includebits/stdc.husingnamespacestd;#defineintlonglongintt,n,l,r,x;// t: 测试用例数, n: 区间个数, l,r: 区间左右端点, x: 当前已使用的最大值signedmain(){ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);// 加速输入输出cint;// 输入测试用例数while(t--)// 处理每个测试用例{cinn;// 输入区间个数x0;// 初始化当前已使用的最大值while(n--)// 处理每个区间{cinlr;// 输入区间[l, r]if(xl)// 如果当前最大值小于区间左端点{coutl ;// 输出左端点xl1;// 更新当前最大值}elseif(xr)// 如果当前最大值大于区间右端点{cout0 ;// 输出0表示无法选择}else// 当前最大值在区间内{coutx ;// 输出当前最大值x;// 当前最大值加1}}coutendl;// 换行}return0;}【运行结果】2 2 1 3 1 4 1 2 3 1 5 1 1 2 3 1 0 2