两台机器独立任务调度题目描述有两台机器A和B以及n个彼此独立的任务。对于第i个任务如果安排到机器A上执行需要a[i]的时间如果安排到机器B上执行需要b[i]的时间。每个任务必须且只能选择一台机器执行。同一台机器在同一时刻最多只能执行一个任务因此分配到同一台机器上的任务需要依次执行机器A和机器B可以并行工作。请合理安排每个任务使得所有任务全部完成所需要的总时间最短。换句话说如果机器A上所有任务的总执行时间为T_A机器B上所有任务的总执行时间为T_B则总完成时间为max⁡(TA,TB)\max(T_A,T_B)max(TA​,TB​)要求最小化这个值。数据范围原题截图没有给出具体范围。如果使用下面的背包 DP可以假设1≤n≤1001\le n\le 1001≤n≤1001≤ai,bi≤10001\le a_i,b_i\le 10001≤ai​,bi​≤1000并且∑ai≤105\sum a_i\le 10^5∑ai​≤105更准确地说这个算法是否可行主要取决于∑ai\sum a_i∑ai​因为时间复杂度为O(n∑ai)O\left(n\sum a_i\right)O(n∑ai​)如果a[i]非常大例如达到10910^9109则不能直接使用这种 DP。输入格式第一行输入一个整数n表示任务数量。接下来n行每行两个整数a[i] b[i]表示第i个任务在机器A上执行需要a[i]时间在机器B上执行需要b[i]时间。输出格式输出一个整数表示完成全部任务所需要的最短时间。样例输入3 2 4 3 2 5 3输出5解释一种最优安排是任务 1 放到机器 A耗时2任务 2 放到机器 A耗时3任务 3 放到机器 B耗时3于是TA235T_A235TA​235TB3T_B3TB​3因此所有任务完成需要max⁡(5,3)5\max(5,3)5max(5,3)5不存在更优方案所以答案为5。思路这道题最关键的一点是任务的执行顺序其实不重要。因为同一台机器上的任务最终都是串行执行所以我们只关心每个任务到底分配给 A还是分配给 B。假设最终分配给机器 A 的任务集合为SSS。那么机器 A 的总执行时间为TA∑i∈SaiT_A\sum_{i\in S}a_iTA​∑i∈S​ai​没有分配给 A 的任务全部分配给 B因此TB∑i∉SbiT_B\sum_{i\notin S}b_iTB​∑i∈/S​bi​我们的目标就是min⁡Smax⁡(∑i∈Sai,∑i∉Sbi)\min_S \max \left( \sum_{i\in S}a_i, \sum_{i\notin S}b_i \right)minS​max(∑i∈S​ai​,∑i∈/S​bi​)这实际上是一个典型的0-1 背包变形。DP 状态设计令dp[j]dp[j]dp[j]表示当前已经处理过一些任务并且机器 A 的总执行时间恰好为j时机器 B 所需要的最小执行时间。例如dp[10] 7表示当前这些任务存在一种分配方式使A 总时间 10 B 总时间 7并且在所有 A 总时间恰好为 10 的方案中B 的 7 是最小的。初始化还没有处理任何任务时A 时间 0 B 时间 0所以dp[0]0dp[0]0dp[0]0其他状态暂时无法达到dp[j]∞dp[j]\inftydp[j]∞状态转移现在考虑第i个任务。它有且只有两种选择。1. 放到机器 B假设之前A 的时间 j B 的时间 dp[j]现在把任务i放到 BA 时间不变 B 时间 b[i]于是dp′[j]dp[j]bidp[j] dp[j]b_idp′[j]dp[j]bi​2. 放到机器 A如果把任务i放到 AA 时间 a[i] B 时间不变所以如果新的 A 时间为j之前的 A 时间应该为j−aij-a_ij−ai​于是dp′[j]dp[j−ai]dp[j] dp[j-a_i]dp′[j]dp[j−ai​]因此完整转移为dp′[j]min⁡(dp[j]bi,dp[j−ai])dp[j] \min \left( dp[j]b_i, dp[j-a_i] \right)dp′[j]min(dp[j]bi​,dp[j−ai​])当然第二种情况要求j≥aij\ge a_ij≥ai​为什么可以压缩成一维这和 0-1 背包完全一样。因为第i个任务只能使用一次所以我们可以让j从大到小枚举for(intj...;j0;--j)这样更新dp[j]时dp[j-a[i]]仍然是上一轮的状态不会重复使用当前任务。最终答案所有任务处理完成以后如果A 总时间 j B 总时间 dp[j]那么全部任务完成的时间就是max⁡(j,dp[j])\max(j,dp[j])max(j,dp[j])因此枚举所有可能的jansmin⁡jmax⁡(j,dp[j])\boxed{ ans \min_j \max(j,dp[j]) }ansjmin​max(j,dp[j])​即可。C 代码#includeiostream#includevector#includealgorithm#includeclimitsusingnamespacestd;intmain(){ios::sync_with_stdio(false);cin.tie(nullptr);intn;cinn;vectorinta(n),b(n);intsumA0;for(inti0;in;i){cina[i]b[i];sumAa[i];}constlonglongINF(1LL60);// dp[j]:// A 的总执行时间恰好为 j 时// B 的最小总执行时间vectorlonglongdp(sumA1,INF);dp[0]0;// 已经处理过的任务在 A 上可能达到的最大时间intcurSum0;for(inti0;in;i){// 倒序枚举类似 0-1 背包for(intjcurSuma[i];j0;--j){longlongputAINF;longlongputBINF;// -------------------------// 情况 1任务 i 放到 B// -------------------------// A 的时间仍然是 jif(jcurSumdp[j]!INF){putBdp[j]b[i];}// -------------------------// 情况 2任务 i 放到 A// -------------------------// 原来 A 的时间为 j - a[i]if(ja[i]j-a[i]curSumdp[j-a[i]]!INF){putAdp[j-a[i]];}dp[j]min(putA,putB);}curSuma[i];}longlongansINF;for(intj0;jsumA;j){if(dp[j]INF)continue;// A 完成需要 j// B 完成需要 dp[j]// 所有任务完成时间取两者最大值ansmin(ans,max((longlong)j,dp[j]));}coutans\n;return0;}复杂度分析设S∑i1naiS\sum_{i1}^{n}a_iS∑i1n​ai​DP 一共有S1S1S1个状态。对于每个任务都需要枚举这些状态因此时间复杂度O(nS)\boxed{O(nS)}O(nS)​即O(n∑ai)\boxed{ O\left(n\sum a_i\right) }O(n∑ai​)​由于使用了一维滚动数组O(S)\boxed{O(S)}O(S)​空间复杂度为O(∑ai)\boxed{ O\left(\sum a_i\right) }O(∑ai​)​一句话记忆这题可以直接记成枚举 A 的总工作时间DP 记录在这个 A 时间下B 最少需要工作多久最后取min(max(A, B))。也就是dp[j] A工作j时间时B所需的最小时间 答案 min(max(j, dp[j]))本质上就是0-1 背包 两台机器负载平衡。关于这道调度题改成处理大数的做法