华为OD机试：项目排期

题目描述

项目组共有 N 个开发人员，项目经理接到了 M 个独立的需求，每个需求的工作量不同，且每个需求只能由一个开发人员独立完成，不能多人合作。

假定各个需求直接无任何先后依赖关系，请设计算法帮助项目经理进行工作安排，使整个项目能用最少的时间交付。

输入描述

第一行输入为 M 个需求的工作量，单位为天，用逗号隔开。

例如：

X1 X2 X3 ... Xm

表示共有 M 个需求，每个需求的工作量分别为X1天，X2天，...，Xm天。其中：

0 < M < 30

0 < Xm < 200

第二行输入为项目组人员数量N

例如：

5

表示共有5名员工，其中 0 < N < 10

输出描述

最快完成所有工作的天数

例如：

25

表示最短需要25天完成所有工作

用例

题目解析

1.首先将输入的需求工作量转换为一个列表，例如输入为"6 2 7 7 9 3 2 1 3 11 4"，则需求工作量列表为[6, 2, 7, 7, 9, 3, 2, 1, 3, 11, 4]。

2.对需求工作量列表进行排序，从小到大排列，以便后续分配给员工。

3.初始化一个变量max_days，用于记录完成所有工作所需的最短天数。

4.遍历需求工作量列表，对于每个需求工作量Xm，将其分配给当前最空闲的员工（即工作时间最短的员工），并更新该员工的工作时间。

5.在每次分配完一个需求后，检查是否已经分配完所有需求，如果是，则更新max_days为当前最大员工工作时间；否则，继续分配下一个需求。

6.最后输出max_days作为结果。

JS算法源码
const rl = require("readline").createInterface({ input: process.stdin });
const readline = async () => (await rl[Symbol.asyncIterator]().next()).value;

(async function () {
  const balls = (await readline()).split(" ").map(Number);
  const n = parseInt(await readline());
  console.log(getResult(balls, n));
})();

function getResult(balls, n) {
  balls.sort((a, b) => b - a);

  let min = balls[0];
  let max = balls.reduce((a, b) => a + b);

  let ans = max;

  while (min <= max) {
    const mid = (min + max) >> 1;

    if (check(balls, 0, new Array(n).fill(0), mid)) {
      ans = mid;
      max = mid - 1;
    } else {
      min = mid + 1;
    }
  }

  return ans;
}

function check(balls, index, buckets, limit) {
  if (index === balls.length) return true;

  const selected = balls[index];

  for (let i = 0; i < buckets.length; i++) {
    if (i > 0 && buckets[i] === buckets[i - 1]) continue;

    if (selected + buckets[i] <= limit) {
      buckets[i] += selected;

      if (check(balls, index + 1, buckets, limit)) return true;

      buckets[i] -= selected;
    }
  }

  return false;
}

Java算法源码
 import java.util.Arrays;
import java.util.Scanner;

public class Main {
    static Integer[] balls;
    static int n;

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        balls = Arrays.stream(sc.nextLine().split(" ")).map(Integer::parseInt).toArray(Integer[]::new);
        n = Integer.parseInt(sc.nextLine());
        System.out.println(getResult());
    }

    public static int getResult() {
        Arrays.sort(balls, (a, b) -> b - a);
        int min = balls[0];
        int max = Arrays.stream(balls).reduce(Integer::sum).get();
        int ans = max;

        while (min <= max) {
            int mid = (min + max) >> 1;
            if (check(0, new int[n], mid)) {
                ans = mid;
                max = mid - 1;
            } else {
                min = mid + 1;
            }
        }
        return ans;
    }

    public static boolean check(int index, int[] buckets, int limit) {
        if (index == balls.length) return true;
        int selected = balls[index];

        for (int i = 0; i < buckets.length; i++) {
            if (i > 0 && buckets[i] == buckets[i - 1]) continue;
            if (selected + buckets[i] <= limit) {
                buckets[i] += selected;
                if (check(index + 1, buckets, limit)) return true;
                buckets[i] -= selected;
            }
        }
        return false;
    }
}

Python算法源码
 
balls = list(map(int, input().split()))
n = int(input())

def check(index, buckets, limit):
    if index == len(balls):
        return True

    selected = balls[index]

    for i in range(len(buckets)):
        if i > 0 and buckets[i] == buckets[i - 1]:
            continue

        if selected + buckets[i] <= limit:
            buckets[i] += selected

            if check(index + 1, buckets, limit):
                return True

            buckets[i] -= selected

    return False

def getResult():
    balls.sort(reverse=True)

    low = balls[0]
    high = sum(balls)
    ans = high

    while low <= high:
        mid = (low + high) >> 1

        if check(0, [0] * n, mid):
            ans = mid
            high = mid - 1
        else:
            low = mid + 1

    return ans

print(getResult())

C算法源码
 #include <stdio.h>
#include <stdlib.h>

#define MAX_M 30
#define MAX_N 10

#define TRUE 1
#define FALSE 0

int balls[MAX_M];
int balls_size = 0;

int buckets_size;

int check(int index, int buckets[], int limit) {
    if (index == balls_size) return TRUE;

    int selected = balls[index];

    for (int i = 0; i < buckets_size; i++) {
        if (i > 0 && buckets[i] == buckets[i - 1]) continue;

        if (selected + buckets[i] <= limit) {
            buckets[i] += selected;

            if (check(index + 1, buckets, limit)) {
                return TRUE;
            }
            buckets[i] -= selected;
        }
    }

    return FALSE;
}

int sum() {
    int sum = 0;
    for (int i = 0; i < balls_size; i++) sum += balls[i];
    return sum;
}

int cmp(const void *a, const void *b) {
    return *((int *) b) - *((int *) a);
}

int main() {
    while (scanf("%d", &balls[balls_size++])) {
        if (getchar() != ' ') break;
    }

    scanf("%d", &buckets_size);

    qsort(balls, balls_size, sizeof(int), cmp);

    int min = balls[0];
    int max = sum();
    int ans = max;

    while (min <= max) {
        int mid = (min + max) >> 1;

        int buckets[MAX_N] = {0};
        if (check(0, buckets, mid)) {
            ans = mid;
            max = mid - 1;
        } else {
            min = mid + 1;
        }
    }

    printf("%d\n", ans);

    return 0;
}