题解

题目描述

实验室需要执行一批计算任务，每个任务会消耗一定的运行时长。现有两台计算机可以执行这些任务，计算机 $A$ 的性能是计算机 $B$ 的两倍，即同样一个任务在计算机 $B$ 上需要的运行时长是 $A$ 的 $2$ 倍。任务需要串行执行，每台计算机同一时刻最多能运行一个任务，同一个任务只能在 $A$ 或 $B$ 上运行完成，不能拆分。

请合理分配这些任务到 $A$ 和 $B$ 上，并返回运行完成所有任务所需的最小时间。

思路

这是一个任务调度问题，需要将一组任务分配到两台性能不同的计算机上，以最小化完成所有任务的总时间。具体来说：

• 计算机性能：计算机 $A$ 的速度是 $B$ 的两倍，即相同任务在 $B$ 上需要的时间是 $A$ 的两倍。
• 目标：最小化所有任务完成所需的总时间，即两台计算机中完成所有任务的最长时间。

将任务分配给计算机 $A$ 或 $B$，需要考虑以下几点：

1. 任务分配的影响：

   • 分配给 $A$ 的任务总时间为 $\text{sum\_A} = \sum t_i$。
   • 分配给 $B$ 的任务总时间为 $\text{sum\_B} = \sum t_i$，但在 $B$ 上运行的总时间为 $2 \times \text{sum\_B}$。

2. 目标函数：最小化 $\max(\text{sum\_A}, 2 \times \text{sum\_B})$。

3. 转化为子集和问题：为了使 $\max(\text{sum\_A}, 2 \times \text{sum\_B})$ 最小化，需要使得 $\text{sum\_A}$ 和 $2 \times \text{sum\_B}$ 尽可能接近。因此，可以将问题转化为寻找一个子集 $S$，使得 $\text{sum\_B} \approx \frac{S}{3}$，其中 $S$ 是所有任务的总和。

4. 算法选择：

   • 这是一个典型的 子集和问题，但由于任务数量和任务时间较大，传统的动态规划方法在时间和空间上不可行。
   • 可以采用 位运算优化的动态规划，利用位运算的高效性来处理大规模的数据。

cpp

#include <bits/stdc++.h>
using namespace std;

int main(){
    // 读取输入任务时间
    string line;
    getline(cin, line);
    vector<int> tasks;
    int t;
    stringstream ss(line);
    while(ss >> t){
        tasks.push_back(t);
    }
    // 计算所有任务的总和
    long long S = 0;
    for(auto &x : tasks) S += x;
    // 使用 bitset 进行子集和计算，最大可能和为1000*1000=1e6
    // 为了节省内存，使用一个动态数组的方式
    vector<bool> dp(S + 1, false);
    dp[0] = true;
    for(auto &task : tasks){
        for(long long j = S; j >= task; j--){
            if(dp[j - task]){
                dp[j] = true;
            }
        }
    }
    // 寻找最接近 S/3 的 sum_B
    long long target = S / 3;
    long long best = 0;
    for(long long i = 0; i <= S; i++) {
        if(dp[i] && abs(i - target) < abs(best - target)){
            best = i;
        }
    }
    // 计算 makespan
    long long sum_B = best;
    long long sum_A = S - sum_B;
    long long makespan = max(sum_A, 2 * sum_B);
    cout << makespan;
}

python

# 读取输入
import sys

def main():
    line = sys.stdin.readline()
    tasks = list(map(int, line.strip().split()))
    S = sum(tasks)
    # 使用集合进行子集和计算
    possible = set()
    possible.add(0)
    for task in tasks:
        new_possible = set()
        for s in possible:
            if s + task <= S:
                new_possible.add(s + task)
        possible.update(new_possible)
    # 寻找最接近 S/3 的 sum_B
    target = S // 3
    best = 0
    for s in possible:
        if abs(s - target) < abs(best - target):
            best = s
    # 计算 makespan
    sum_B = best
    sum_A = S - sum_B
    makespan = max(sum_A, 2 * sum_B)
    print(makespan)

if __name__ == "__main__":
    main()

java

import java.util.*;
import java.io.*;

public class Main {
    public static void main(String[] args) throws IOException{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String line = br.readLine();
        String[] parts = line.trim().split("\\s+");
        int n = parts.length;
        int[] tasks = new int[n];
        long S = 0;
        for(int i=0;i<n;i++){
            tasks[i] = Integer.parseInt(parts[i]);
            S += tasks[i];
        }
        // 使用 BitSet 进行子集和计算
        BitSet bs = new BitSet((int)(S + 1));
        bs.set(0); // 初始时，和为0是可达的
        for(int task : tasks){
            BitSet shifted = shiftLeft(bs, task, (int)(S + 1));
            bs.or(shifted);
        }
        // 寻找最接近 S/3 的 sum_B
        long target = S / 3;
        long best = 0;
        for(int i=0;i<=S;i++){
            if(bs.get(i)){
                if(Math.abs(i - target) < Math.abs(best - target)){
                    best = i;
                }
            }
        }
        // 计算 makespan
        long sum_B = best;
        long sum_A = S - sum_B;
        long makespan = Math.max(sum_A, 2 * sum_B);
        System.out.println(makespan);
    }
    
    /**
     * 将 BitSet 左移 n 位
     * @param bs 原始 BitSet
     * @param n 左移的位数
     * @param size BitSet 的大小
     * @return 左移后的 BitSet
     */
    public static BitSet shiftLeft(BitSet bs, int n, int size){
        BitSet shifted = new BitSet(size);
        for(int i = bs.nextSetBit(0); i >=0 && i < size; i = bs.nextSetBit(i+1)){
            if(i + n < size){
                shifted.set(i + n);
            }
        }
        return shifted;
    }
}

题目内容

实验室需要执行一批计算任务，每个任务会消耗一定的运行时长。

现在有两台计算机可以执行这些计算任务，但是两个计算机的性能并不相同:

• 计算机 $A$ 是计算机 $B$ 性能的两倍，即同样一个任务在计算机 $B$ 上需要的运行时长是 $A$ 的 $2$ 倍。

任务是串行的，每个计算机同一时刻最多能运行一个任务;同一个任务只能在 $A$ 或 $B$ 上一次运行完成，不能拆分成多段。

请你合理分配这些任务到 $A$ 和 $B$ 上，并返回运行完成这些计算任务所需要的最小时间。

输入描述

1.每个计算任务在计算机 $A$ 上运行需要的时长，以空格隔开。

2.运行时长单位是分钟，都是正整数，取值范围是 $[1,1000]$ 。

3.任务总数范围是 $[1,1000]$ 。

输出描述

所有计算任务全部完成需要的最小分钟数。

样例1

输入

20 15 10

输出

30

说明

$A$ 上运行第 $1、3$ 个作业，耗时 $30$ 分钟

$B$ 上运行第 $2$ 个作业，耗时 $15*2=30$ 分钟

总共耗时 $30$ 分钟。

样例2

输入

6 15 22 13

输出

38

说明

$A$ 上运行第 $2、3$ 个作业，耗时 $37$ 分钟

$B$ 上运行第 $1、4$ 个作业，耗时 $38$ 分钟

总共耗时 $38$ 分钟。