题目描述有nnn个作业JiJ_iJi每个作业有一个服务时间sis_isi和一个截止期限did_idi。服务工程师从时间000开始处理作业一次只能处理一个作业且作业不可中断。若作业JiJ_iJi在时间CiC_iCi完成则其延迟定义为max{0,Ci−di}\max\{0, C_i - d_i\}max{0,Ci−di}。目标是为所有作业找到一个调度顺序使得所有作业延迟中最大的两个延迟之和最小并输出这个最小值。若作业数量不足两个则不足部分的延迟视为000。输入格式第一行包含一个整数TTT表示测试用例的数量。接下来每个测试用例的输入格式如下第一行包含一个整数nnn1≤n≤5001 \le n \le 5001≤n≤500表示作业的数量。接下来nnn行每行包含两个整数sis_isi和did_idi满足1≤si≤di≤10,0001 \le s_i \le d_i \le 10{,}0001≤si≤di≤10,000。输出格式对于每个测试用例输出一行一个整数表示最小的两个最大延迟之和。样例输入3 6 1 7 4 7 2 4 2 15 3 5 3 8 7 2 17 2 11 3 4 3 20 1 20 4 7 5 14 10 2 5 2 9 5 10 3 11 3 4 4 21 1 7 2 9 2 11 2 23输出7 0 14题目分析本题要求最小化所有作业延迟中最大的两个值之和。直接枚举所有n!n!n!种调度顺序显然不可行。我们需要利用调度问题的特殊性质来降低复杂度。首先考虑一个简化问题如果只需要最小化最大延迟那么按照截止期限升序调度EDD\texttt{EDD}EDD规则是最优的。这是因为EDD\texttt{EDD}EDD规则可以最小化最大延迟。对于本题目标是最小化两个最大延迟之和这比单纯最小化最大延迟更复杂。一个重要观察是在最优调度中除了延迟最大的那个作业以外其余作业可以按EDD\texttt{EDD}EDD规则调度。换句话说我们可以枚举哪一个作业是“被牺牲”的那个即延迟最大的作业然后将其放在最后执行其余作业按截止期限升序执行。这样构造的调度虽然不一定是全局最优的但通过枚举所有可能的候选作业可以覆盖最优解。然而直接枚举所有作业作为候选仍然不够高效。通过进一步分析可以发现只需要枚举贪心序列中某个关键位置之前的作业即可。这个关键位置ppp可以通过第一次贪心扫描确定。解题思路第一步贪心预处理首先将所有作业按截止期限did_idi升序排序。然后按照这个顺序模拟执行计算每个作业的延迟。在模拟过程中我们维护两个变量first\textit{first}first当前遇到的最大延迟second\textit{second}second当前遇到的第二大延迟同时记录位置ppp其更新规则为每当当前的延迟大于等于当前的second\textit{second}second时就将ppp更新为当前位置iii。这样ppp就是最后一次更新第二大延迟的位置。这个ppp的含义是在贪心序列中从ppp之后的所有作业它们的延迟都不超过此时记录的second\textit{second}second。因此只有位置在ppp之前的作业才有可能通过移动来改善结果。第二步枚举关键作业对于每个iii从000到p−1p-1p−1我们尝试将作业iii移动到最后执行其余作业保持原来的相对顺序仍然是按截止期限升序。然后重新计算这种调度下的最大延迟和第二大延迟之和。具体计算方式如下初始化时间为000最大延迟first0\textit{first} 0first0第二大延迟second0\textit{second} 0second0。遍历位置从000到ppp注意是到ppp不是到n−1n-1n−1如果当前位置等于iii则跳过因为该作业被移到末尾。否则累加当前作业的服务时间计算延迟penaltymax(0,time−dj)\textit{penalty} \max(0, \textit{time} - d_j)penaltymax(0,time−dj)。更新first\textit{first}first和second\textit{second}second。最后处理被移动的作业iii将其服务时间累加到时间上计算其延迟并更新first\textit{first}first和second\textit{second}second。返回firstsecond\textit{first} \textit{second}firstsecond。第三步取最小值初始答案即为第一次贪心扫描得到的firstsecond\textit{first} \textit{second}firstsecond。然后对于每个i∈[0,p−1]i \in [0, p-1]i∈[0,p−1]计算handle(i)\texttt{handle}(i)handle(i)并更新答案的最小值。正确性说明为什么只枚举ipi pip就够了因为ppp是贪心过程中最后一个使当前延迟超过second\textit{second}second的位置。位于ppp之后的作业其延迟都不超过当时的second\textit{second}second移动它们不会改善两个最大延迟之和。为什么只需要重新计算到位置ppp因为ppp之后的所有作业在移动后的调度中仍然保持原来的顺序且它们的延迟不会超过移动后的first\textit{first}first和second\textit{second}second。由于我们只关心最大的两个延迟ppp之后的部分不会影响最终结果。复杂度分析排序O(nlogn)O(n \log n)O(nlogn)第一次贪心扫描O(n)O(n)O(n)枚举最多O(n)O(n)O(n)次调用handle\texttt{handle}handle每次handle\texttt{handle}handle执行O(p)O(n)O(p) O(n)O(p)O(n)次操作总时间复杂度O(n2)O(n^2)O(n2)当n500n 500n500时完全可行代码实现// Installations// UVa ID: 1467// Verdict: Accepted// Submission Date: 2026-06-03// UVa Run Time: 0.000s//// 版权所有C2016邱秋。metaphysis # yeah dot net#includebits/stdc.husingnamespacestd;structJob{ints,d;};intn,p;vectorJobjobs;boolcmpByDeadline(constJoba,constJobb){returna.db.d;}inthandle(intx){inttime0,first0,second0;for(inti0;ip;i){if(ix)continue;timejobs[i].s;intpenaltymax(0,time-jobs[i].d);if(penaltysecond){secondpenalty;if(secondfirst)swap(first,second);}}timejobs[x].s;intpenaltymax(0,time-jobs[x].d);if(penaltysecond){secondpenalty;if(secondfirst)swap(first,second);}returnfirstsecond;}intsolve(){sort(jobs.begin(),jobs.end(),cmpByDeadline);inttime0,first0,second0;for(inti0;in;i){timejobs[i].s;intpenaltymax(0,time-jobs[i].d);if(penaltysecond){secondpenalty;pi;// 关键每次都更新 p 为当前位置}if(secondfirst)swap(first,second);}intansfirstsecond;for(inti0;ip;i)ansmin(ans,handle(i));returnans;}intmain(){ios::sync_with_stdio(false);cin.tie(nullptr);intT;cinT;while(T--){cinn;jobs.resize(n);for(inti0;in;i)cinjobs[i].sjobs[i].d;coutsolve()\n;}return0;}总结本题的核心技巧在于利用EDD\texttt{EDD}EDD规则除了可能被移动的作业外其余作业按截止期限升序调度是最优的。确定关键位置ppp通过第一次贪心扫描找到最后一次更新第二大延迟的位置将枚举范围缩小到[0,p−1][0, p-1][0,p−1]。只重算前p1p1p1个作业因为ppp之后的部分不会影响两个最大延迟的值。这道题展示了如何将贪心思想与有限的暴力枚举相结合在保证正确性的同时将复杂度控制在O(n2)O(n^2)O(n2)。这种“贪心预处理 局部枚举”的模式在调度优化问题中具有广泛的适用性。
