网站备案 类型建站服务外贸

网站备案 类型,建站服务外贸,net网站开发学习,山东做网站费用题目描述 John\texttt{John}John 是小镇上唯一的牧师。每年的 101010 月 262626 日是他最忙碌的一天#xff0c;因为传说在这一天结婚的夫妇会受到爱神的祝福。今年有 NNN 对夫妇计划在这一天举行婚礼#xff0c;第 iii 对夫妇的婚礼计划在时间 SiS_iSi​ 到 TiT_iTi​ 进行。…题目描述John\texttt{John}John是小镇上唯一的牧师。每年的101010月262626日是他最忙碌的一天因为传说在这一天结婚的夫妇会受到爱神的祝福。今年有NNN对夫妇计划在这一天举行婚礼第iii对夫妇的婚礼计划在时间SiS_iSi​到TiT_iTi​进行。根据传统每场婚礼都必须有一个特殊仪式夫妇需要站在牧师面前接受祝福。这个仪式必须满足以下条件仪式必须连续进行不能中断。仪式的持续时间必须超过婚礼总时长的一半。John\texttt{John}John只能在整数时间点开始或离开仪式。John\texttt{John}John不能同时主持两个仪式但可以在一个仪式结束后立即开始下一个。请你判断John\texttt{John}John是否能够安排出时间主持所有NNN场婚礼的特殊仪式。输入格式输入包含多个测试用例以一行一个000结束。每个测试用例的第一行是一个整数NNN1≤N≤100,0001 \le N \le 100,0001≤N≤100,000表示婚礼的数量。接下来NNN行每行包含两个整数SiS_iSi​和TiT_iTi​0≤SiTi≤21474836470 \le S_i T_i \le 21474836470≤Si​Ti​≤2147483647表示第iii场婚礼的开始和结束时间。输出格式对于每个测试用例如果John\texttt{John}John可以主持所有仪式输出YES否则输出NO。样例输入3 1 5 2 4 3 6 2 1 5 4 6 0样例输出NO YES题目分析本题的核心是区间安排问题但与传统活动安排不同的是每场婚礼的仪式长度不是固定的而是根据婚礼的时长动态计算得到。1. 仪式长度的计算对于一场婚礼[Si,Ti][S_i, T_i][Si​,Ti​]其总时长为Ti−SiT_i - S_iTi​−Si​。仪式必须超过时长的一半即仪式时长Ti−Si2 \text{仪式时长} \frac{T_i - S_i}{2}仪式时长2Ti​−Si​​因为仪式必须在整数时间点开始和结束所以我们可以将上述条件转化为最短仪式时长leni⌊Ti−Si2⌋1 \texttt{len}_i \left\lfloor \frac{T_i - S_i}{2} \right\rfloor 1leni​⌊2Ti​−Si​​⌋1这里⌊⋅⌋\lfloor \cdot \rfloor⌊⋅⌋表示向下取整。加111是为了确保严格大于一半。2. 仪式可行的开始时间区间仪式长度为leni\texttt{len}_ileni​必须在[Si,Ti][S_i, T_i][Si​,Ti​]内连续进行。设仪式开始时间为ttt则必须满足Si≤t且tleni≤Ti S_i \le t \quad \text{且} \quad t \texttt{len}_i \le T_iSi​≤t且tleni​≤Ti​由tleni≤Tit \texttt{len}_i \le T_itleni​≤Ti​可得t≤Ti−leni t \le T_i - \text{len}_it≤Ti​−leni​因此仪式开始时间ttt必须落在区间[Si, Ti−leni] [S_i, \; T_i - \text{len}_i][Si​,Ti​−leni​]我们称LiSiL_i S_iLi​Si​为最早开始时间RiTi−leniR_i T_i - \texttt{len}_iRi​Ti​−leni​为最晚开始时间。3. 问题转化现在问题转化为有NNN个活动每个活动需要连续进行leni\texttt{len}_ileni​单位时间且必须开始于[Li,Ri][L_i, R_i][Li​,Ri​]区间内。问是否存在一种安排顺序使得所有活动不重叠。这是一个带时间窗的活动安排问题可以用贪心算法解决。解题思路贪心策略我们按照最晚开始时间RiR_iRi​升序排序。理由如下如果某个活动的RiR_iRi​很早说明它必须尽早开始否则就来不及了。贪心安排时我们总是尽量早地开始每个活动以便为后面的活动留出更多时间。安排步骤排序将所有婚礼按照RiR_iRi​最晚开始时间从小到大排序。初始化当前时间设currentTime 0表示 John 当前可用的最早开始时间。依次安排对于每个婚礼iii计算其实际开始时间startTimemax⁡(currentTime, Li) \texttt{startTime} \max(\texttt{currentTime}, \; L_i)startTimemax(currentTime,Li​)即不能早于LiL_iLi​也不能早于当前可用时间。检查是否可行如果startTimeRi\texttt{startTime} R_istartTimeRi​说明无法在允许的时间窗内开始直接返回NO。更新当前时间currentTime startTime len_i。如果所有婚礼都安排成功输出YES。正确性证明按RiR_iRi​排序后如果某个婚礼无法安排那么无论如何调整顺序它都无法被安排因为它的时间窗已经是最宽松的“最晚开始时间”。贪心选择最早可能的开始时间不会使后续安排变差因为给后面的活动留出了更多的空闲时间。时间复杂度排序O(Nlog⁡N)O(N \log N)O(NlogN)贪心安排O(N)O(N)O(N)总复杂度O(Nlog⁡N)O(N \log N)O(NlogN)在N≤100,000N \le 100,000N≤100,000时可行。代码实现// Priest Johns Busiest Day// UVa ID: 1420// Verdict: Accepted// Submission Date: 2025-12-17// UVa Run Time: 0.060s//// 版权所有C2025邱秋。metaphysis # yeah dot net#includebits/stdc.husingnamespacestd;structWedding{longlongstart,endLimit,len;};boolcompare(constWeddinga,constWeddingb){returna.endLimitb.endLimit;}intmain(){ios::sync_with_stdio(false);cin.tie(nullptr);intn;while(cinnn!0){vectorWeddingweddings(n);for(inti0;in;i){longlongs,t;cinst;longlonglen(t-s)/21;// 最短仪式时长weddings[i].starts;weddings[i].endLimitt-len;// 最晚开始时间weddings[i].lenlen;}sort(weddings.begin(),weddings.end(),compare);longlongcurrentTime0;boolpossibletrue;for(constautow:weddings){longlongstartTimemax(currentTime,w.start);if(startTimew.endLimit){possiblefalse;break;}currentTimestartTimew.len;}cout(possible?YES:NO)\n;}return0;}总结本题的关键在于将原问题转化为带时间窗的连续活动安排问题并通过计算得到每个活动的最短长度和最晚开始时间。贪心策略按最晚开始时间排序并尽量早开始能够高效地判断是否存在可行安排。这种方法不仅思路清晰而且代码简洁时间复杂度为O(Nlog⁡N)O(N \log N)O(NlogN)适合处理大规模输入。