AI驱动Google Workspace命令行工具开发实战
2026/7/26 5:31:28
题目描述
有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，表示测试用例的数量。接下来每个测试用例的输入格式如下：
- 第一行包含一个整数nnn（1≤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，最大延迟first=0\textit{first} = 0first=0，第二大延迟second=0\textit{second} = 0second=0。
- 遍历位置从000到ppp（注意是到ppp，不是到n−1n-1n−1）：
- 如果当前位置等于iii，则跳过（因为该作业被移到末尾）。
- 否则，累加当前作业的服务时间，计算延迟penalty=max(0,time−dj)\textit{penalty} = \max(0, \textit{time} - d_j)penalty=max(0,time−dj)。
- 更新first\textit{first}first和second\textit{second}second。
- 最后处理被移动的作业iii：将其服务时间累加到时间上，计算其延迟，并更新first\textit{first}first和second\textit{second}second。
- 返回first+second\textit{first} + \textit{second}first+second。
第三步：取最小值
初始答案即为第一次贪心扫描得到的first+second\textit{first} + \textit{second}first+second。然后对于每个i∈[0,p−1]i \in [0, p-1]i∈[0,p−1]，计算handle(i)\texttt{handle}(i)handle(i)并更新答案的最小值。
正确性说明
- 为什么只枚举i<pi < pi<p就够了？因为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)，当n=500n = 500n=500时完全可行
代码实现
// Installations// UVa ID: 1467// Verdict: Accepted// Submission Date: 2026-06-03// UVa Run Time: 0.000s//// 版权所有（C）2016，邱秋。metaphysis # yeah dot net#include<bits/stdc++.h>usingnamespacestd;structJob{ints,d;};intn,p;vector<Job>jobs;boolcmpByDeadline(constJob&a,constJob&b){returna.d<b.d;}inthandle(intx){inttime=0,first=0,second=0;for(inti=0;i<=p;++i){if(i==x)continue;time+=jobs[i].s;intpenalty=max(0,time-jobs[i].d);if(penalty>=second){second=penalty;if(second>first)swap(first,second);}}time+=jobs[x].s;intpenalty=max(0,time-jobs[x].d);if(penalty>=second){second=penalty;if(second>first)swap(first,second);}returnfirst+second;}intsolve(){sort(jobs.begin(),jobs.end(),cmpByDeadline);inttime=0,first=0,second=0;for(inti=0;i<n;++i){time+=jobs[i].s;intpenalty=max(0,time-jobs[i].d);if(penalty>=second){second=penalty;p=i;// 关键：每次都更新 p 为当前位置}if(second>first)swap(first,second);}intans=first+second;for(inti=0;i<p;++i)ans=min(ans,handle(i));returnans;}intmain(){ios::sync_with_stdio(false);cin.tie(nullptr);intT;cin>>T;while(T--){cin>>n;jobs.resize(n);for(inti=0;i<n;++i)cin>>jobs[i].s>>jobs[i].d;cout<<solve()<<'\n';}return0;}总结
本题的核心技巧在于：
- 利用EDD\texttt{EDD}EDD规则：除了可能被移动的作业外，其余作业按截止期限升序调度是最优的。
- 确定关键位置ppp：通过第一次贪心扫描找到最后一次更新第二大延迟的位置，将枚举范围缩小到[0,p−1][0, p-1][0,p−1]。
- 只重算前p+1p+1p+1个作业：因为ppp之后的部分不会影响两个最大延迟的值。
这道题展示了如何将贪心思想与有限的暴力枚举相结合，在保证正确性的同时将复杂度控制在O(n2)O(n^2)O(n2)。这种“贪心预处理 + 局部枚举”的模式在调度优化问题中具有广泛的适用性。