尧图网络 高端网站定制 · 原创设计
免费咨询热线
400-888-6620
免费获取方案
题解:学而思编程 食堂排队
【题目来源】学而思编程食堂排队【题目描述】某班有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
RELATED

相关推荐

LRU Cache:面试必考设计题

LRU Cache:面试必考设计题

LRU Cache:面试必考设计题 1. 直观类比:手机后台应用列表 打开手机的多任务界面——你最近打开的 App 排在前面,很久没用的沉到后面。当后台 App 太多(容量满了),系统杀掉排在最末尾的那个。 这就是 LRU&am…

📅 2026/10/30 14:24:12
AI 复制内容带乱码太糟心?AI 导出鸭一键解决格式错乱与乱码难题

AI 复制内容带乱码太糟心?AI 导出鸭一键解决格式错乱与乱码难题

AI复制内容带乱码太糟心?AI导出鸭一键解决格式错乱与乱码难题告别AI复制内容带乱码困扰,AI导出鸭让导出内容完整无乱码更省心AI复制内容带乱码频发?AI导出鸭高效破解各类AI内容导出乱码问题 前言 作为常年和各类AI工具打交道的开发者、内容创…

📅 2026/10/31 15:14:55
LP5812与PIC18LF26K80实现RGB LED智能控制方案

LP5812与PIC18LF26K80实现RGB LED智能控制方案

1. 项目背景与核心价值在当今的智能硬件和物联网设备中,灯光效果已经远远超越了简单的照明功能,成为提升用户体验的关键交互媒介。LP5812作为一款专业的三通道RGB LED驱动芯片,配合PIC18LF26K80微控制器,能够实现从基础色彩控制到…

📅 2026/10/31 9:14:29
MORE NEWS

更多资讯

📰

沧州肃宁县电工证怎么考才不被中介坑?考前押题资料别错过

沧州肃宁县电工证怎么考才不被中介坑?考前押题资料别错过 不知道去哪报名怕被中介坑?沧州肃宁县电工证考试流程复杂、报名渠道真假难辨,很多想考电工证的小伙伴都遇到过类似的问题。尤其是刚接触这个行业的新手,最容易被一些“代办机构”忽悠,不仅花钱还…

📰

南宁1300考电工证通过率揭秘:电工证怎么考才能稳过?

南宁1300考电工证通过率揭秘:电工证怎么考才能稳过? 你是不是也正为找工作发愁?特种作业证不全,连面试都过不了,南宁1300考电工证成了不少人的刚需。别急,今天就带你从零开始,看看电工证到底怎么考、怎么报,还能避开哪些坑。…

📰

电工证与建筑电工证郑州报考避坑指南:学历不高怕报不上名?看这篇就够了

电工证与建筑电工证郑州报考避坑指南:学历不高怕报不上名?看这篇就够了 你是不是也这样?学历不高,担心自己报不了电工证或者建筑电工证,生怕被拒之门外。其实不然,只要掌握正确的报考流程和准备材料,即使是初中毕业,也能顺利拿到证书。今天这篇文章,…

📰

文登在哪考低压电工证通过率揭秘:证书过期了不知道怎么复审延期怎么办

文登在哪考低压电工证通过率揭秘:证书过期了不知道怎么复审延期怎么办 证书过期了不知道怎么复审延期?别慌,文登低压电工证复审流程其实没你想象的那么复杂。今天就带你一步步搞清楚文登低压电工证在哪考,到期如何换证,以及通过率到底怎么样。…

📰

舒城县办电工证通过率揭秘,没证真不能上岗找工作

舒城县办电工证通过率揭秘,没证真不能上岗找工作 你是不是也遇到过这种情况,拿着简历去面试,对方看了一眼就说“没有电工证不能上岗”?这不是危言耸听,这是现实。现在大多数工地、工厂、电力项目等岗位都明确要求特种作业证,尤其是 舒城县办电工证…

📰

新疆电工证要体检吗真实经历告诉你怎么选培训机构

新疆电工证要体检吗真实经历告诉你怎么选培训机构 刚拿到特种作业证就能上岗,这是很多刚毕业或想转行的小伙伴的共同愿望。可问题是, 新疆电工证要体检吗…

TODAY

今日更新

THIS WEEK

本周精选

THIS MONTH

本月热门

读完文章,想聊聊您的网站?

告诉我们您的行业与需求,资深顾问一对一梳理方案与报价,全程免费。

📞 💬