UVa 1420 Priest John‘s Busiest Day

题目描述

John\texttt{John}John是小镇上唯一的牧师。每年的101010月262626日是他最忙碌的一天，因为传说在这一天结婚的夫妇会受到爱神的祝福。今年有NNN对夫妇计划在这一天举行婚礼，第iii对夫妇的婚礼计划在时间SiS_iSi​到TiT_iTi​进行。

根据传统，每场婚礼都必须有一个特殊仪式，夫妇需要站在牧师面前接受祝福。这个仪式必须满足以下条件：

1. 仪式必须连续进行，不能中断。
2. 仪式的持续时间必须超过婚礼总时长的一半。
3. John\texttt{John}John只能在整数时间点开始或离开仪式。
4. John\texttt{John}John不能同时主持两个仪式，但可以在一个仪式结束后立即开始下一个。

请你判断John\texttt{John}John是否能够安排出时间，主持所有NNN场婚礼的特殊仪式。

输入格式

• 输入包含多个测试用例，以一行一个000结束。
• 每个测试用例的第一行是一个整数NNN（1≤N≤100,0001 \le N \le 100,0001≤N≤100,000），表示婚礼的数量。
• 接下来NNN行，每行包含两个整数SiS_iSi​和TiT_iTi​（0≤Si<Ti≤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且t+leni≤Ti S_i \le t \quad \text{且} \quad t + \texttt{len}_i \le T_iSi​≤t且t+leni​≤Ti​

由t+leni≤Tit + \texttt{len}_i \le T_it+leni​≤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​]

我们称Li=SiL_i = S_iLi​=Si​为最早开始时间，Ri=Ti−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​很早，说明它必须尽早开始，否则就来不及了。
• 贪心安排时，我们总是尽量早地开始每个活动，以便为后面的活动留出更多时间。

安排步骤

1. 排序：将所有婚礼按照RiR_iRi​（最晚开始时间）从小到大排序。
2. 初始化当前时间：设currentTime = 0，表示 John 当前可用的最早开始时间。
3. 依次安排：
   • 对于每个婚礼iii，计算其实际开始时间：
     startTime=max⁡(currentTime, Li) \texttt{startTime} = \max(\texttt{currentTime}, \; L_i)startTime=max(currentTime,Li​)
     即不能早于LiL_iLi​，也不能早于当前可用时间。
   • 检查是否可行：如果startTime>Ri\texttt{startTime} > R_istartTime>Ri​，说明无法在允许的时间窗内开始，直接返回NO。
   • 更新当前时间：currentTime = startTime + len_i。
4. 如果所有婚礼都安排成功，输出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 John's Busiest Day// UVa ID: 1420// Verdict: Accepted// Submission Date: 2025-12-17// UVa Run Time: 0.060s//// 版权所有（C）2025，邱秋。metaphysis # yeah dot net#include<bits/stdc++.h>usingnamespacestd;structWedding{longlongstart,endLimit,len;};boolcompare(constWedding&a,constWedding&b){returna.endLimit<b.endLimit;}intmain(){ios::sync_with_stdio(false);cin.tie(nullptr);intn;while(cin>>n&&n!=0){vector<Wedding>weddings(n);for(inti=0;i<n;++i){longlongs,t;cin>>s>>t;longlonglen=(t-s)/2+1;// 最短仪式时长weddings[i].start=s;weddings[i].endLimit=t-len;// 最晚开始时间weddings[i].len=len;}sort(weddings.begin(),weddings.end(),compare);longlongcurrentTime=0;boolpossible=true;for(constauto&w:weddings){longlongstartTime=max(currentTime,w.start);if(startTime>w.endLimit){possible=false;break;}currentTime=startTime+w.len;}cout<<(possible?"YES":"NO")<<"\n";}return0;}

总结

本题的关键在于将原问题转化为带时间窗的连续活动安排问题，并通过计算得到每个活动的最短长度和最晚开始时间。贪心策略（按最晚开始时间排序，并尽量早开始）能够高效地判断是否存在可行安排。

这种方法不仅思路清晰，而且代码简洁，时间复杂度为O(Nlog⁡N)O(N \log N)O(NlogN)，适合处理大规模输入。