两台机器独立任务调度

题目描述

有两台机器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

于是：

TA=2+3=5T_A=2+3=5TA​=2+3=5TB=3T_B=3TB​=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放到 B：

A 时间不变 B 时间 += b[i]

于是：

dp′[j]=dp[j]+bidp'[j] = dp[j]+b_idp′[j]=dp[j]+bi​

2. 放到机器 A

如果把任务i放到 A：

A 时间 += 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=...;j>=0;--j)

这样更新dp[j]时，dp[j-a[i]]仍然是上一轮的状态，不会重复使用当前任务。

最终答案

所有任务处理完成以后，如果：

A 总时间 = j B 总时间 = dp[j]

那么全部任务完成的时间就是：

max⁡(j,dp[j])\max(j,dp[j])max(j,dp[j])

因此枚举所有可能的j：

ans=min⁡jmax⁡(j,dp[j])\boxed{ ans= \min_j \max(j,dp[j]) }ans=jmin​max(j,dp[j])​

即可。

C++ 代码

#include<iostream>#include<vector>#include<algorithm>#include<climits>usingnamespacestd;intmain(){ios::sync_with_stdio(false);cin.tie(nullptr);intn;cin>>n;vector<int>a(n),b(n);intsumA=0;for(inti=0;i<n;++i){cin>>a[i]>>b[i];sumA+=a[i];}constlonglongINF=(1LL<<60);// dp[j]:// A 的总执行时间恰好为 j 时，// B 的最小总执行时间vector<longlong>dp(sumA+1,INF);dp[0]=0;// 已经处理过的任务在 A 上可能达到的最大时间intcurSum=0;for(inti=0;i<n;++i){// 倒序枚举，类似 0-1 背包for(intj=curSum+a[i];j>=0;--j){longlongputA=INF;longlongputB=INF;// -------------------------// 情况 1：任务 i 放到 B// -------------------------// A 的时间仍然是 jif(j<=curSum&&dp[j]!=INF){putB=dp[j]+b[i];}// -------------------------// 情况 2：任务 i 放到 A// -------------------------// 原来 A 的时间为 j - a[i]if(j>=a[i]&&j-a[i]<=curSum&&dp[j-a[i]]!=INF){putA=dp[j-a[i]];}dp[j]=min(putA,putB);}curSum+=a[i];}longlongans=INF;for(intj=0;j<=sumA;++j){if(dp[j]==INF)continue;// A 完成需要 j// B 完成需要 dp[j]// 所有任务完成时间取两者最大值ans=min(ans,max((longlong)j,dp[j]));}cout<<ans<<'\n';return0;}

复杂度分析

设：

S=∑i=1naiS=\sum_{i=1}^{n}a_iS=∑i=1n​ai​

DP 一共有：

S+1S+1S+1

个状态。

对于每个任务，都需要枚举这些状态，因此时间复杂度：

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 背包 + 两台机器负载平衡。

关于这道调度题

• 改成处理大数的做法