(C卷,100分)- 部门人力分配（Java & JS & Python & C）

题目描述

部门在进行需求开发时需要进行人力安排。

当前部门需要完成 N 个需求，需求用 requirements 表述，requirements[i] 表示第 i 个需求的工作量大小，单位：人月。

这部分需求需要在 M 个月内完成开发，进行人力安排后每个月人力时固定的。

目前要求每个月最多有2个需求开发，并且每个月需要完成的需求不能超过部门人力。

请帮助部门评估在满足需求开发进度的情况下，每个月需要的最小人力是多少？

输入描述

输入为 M 和 requirements，M 表示需求开发时间要求，requirements 表示每个需求工作量大小，N 为 requirements长度，

• 1 ≤ N/2 ≤ M ≤ N ≤ 10000
• 1 ≤ requirements[i] ≤ 10^9

输出描述

对于每一组测试数据，输出部门需要人力需求，行末无多余的空格

用例

题目解析

本题是将二分和双指针考点结合在了一起。

本题我们可以换个说法：

目前有 N 个人（N个需求），

每个人的体重为requirements[i]，（每个需求开发需要的人力为requirements[i]）

以及 M 辆自行车（M个月开发），

每辆自行车至多坐两人（每个月至多开发两个需求），

现在想要用 M 辆自行车带走 N 个人，问每辆自行车的限重至少是多少？（M个月开发完N个需求，每个月至少需要多少人力）

每辆自行车载重：

• min 至少是 1st_max(requirements)，这样才能保证最重的人可以单独骑一辆自行车
• max 至多是 1st_max(requirements) + 2nd_max(requirements)，这样最重的两个人可以骑在一辆自行车商

我们可以在该[min, max]范围内二分找中间值mid，作为每辆自行车的限重去尝试（check）,看对应限重下至少需要多少辆自行车。

比如二分取中间值mid作为每辆自行车的限重，并将体重数组requirements升序排序，定义两个指针L，R，初始化L = 0，R=requirements.length -1。

那么L指向的就是体重最轻的人，R指向的就是体重最重的人。

• 如果 requirement[L] + requirement[R] <= mid，则说明最轻的人和最重的人可以坐一辆自行车，然后L++，R–，用车数量 need++
• 如果 requirement[L] + requirement[R] > mid，则说明最重的人只能一个人坐一辆自行车，无法搭配其他人，然后仅 R– ，用车数量 need++

按上面逻辑继续进行，直到L > R时，即所有人都坐上了自行车时停止，此时我们比较need和M，

• 如果need <= M，则说明 mid 限重可以满足M辆车带走所有人，此时mid就是一个本题的一个可能解，但不一定时最优解，我们应该继续尝试更小的限重，即max = mid – 1
• 如果need > M，则说明 mid 限重无法满足M辆车带走所有人，因此我们需要更大的限重，即 min = mid + 1

然后继续二分取中间值作为限重带入前面双指针逻辑check。

另外本题需要注意整型溢出问题。

JS算法源码

const rl = require("readline").createInterface({ input: process.stdin });
var iter = rl[Symbol.asyncIterator]();
const readline = async () => (await iter.next()).value;

// 输入处理
void (async function () {
  const m = parseInt(await readline());
  const requirements = (await readline()).split(" ").map(Number);

  console.log(getResult(m, requirements));
})();

function getResult(m, requirements) {
  requirements.sort((a, b) => a - b);

  const n = requirements.length;

  // 每辆自行车的限重 至少是 最重的那个人的体重
  let min = requirements[n - 1];
  // 每辆自行车的限重 至多是 最重的和次重的那两个的体重
  let max = requirements[n - 2] + requirements[n - 1];

  let ans = max;

  // 二分取中间值
  while (min <= max) {
    const mid = Math.floor((min + max) / 2); // 注意这里不能使用 >> 1 运算，会出现整型溢出

    if (check(mid, m, requirements)) {
      // 如果mid限重，可以满足m辆车带走n个人，则mid就是一个可能解，但不一定是最优解
      ans = mid;
      // 继续尝试更小的限重，即缩小右边界
      max = mid - 1;
    } else {
      // 如果mid限重，不能满足m辆车带走n个人，则mid限重小了，我们应该尝试更大的限重，即扩大左边界
      min = mid + 1;
    }
  }

  return ans;
}

/**
 * @param limit 每辆自行车的限重
 * @param m m辆自行车
 * @param requirements n个人的体重数组
 * @return m辆自行车，每辆限重limit的情况下，能否带走n个人
 */
function check(limit, m, requirements) {
  let l = 0; // 指向体重最轻的人
  let r = requirements.length - 1; // 指向体重最重的人

  // 需要的自行车数量
  let need = 0;

  while (l <= r) {
    // 如果最轻的人和最重的人可以共享一辆车，则l++,r--，
    // 否则最重的人只能单独坐一辆车，即仅r--
    if (requirements[l] + requirements[r] <= limit) {
      l++;
    }
    r--;
    // 用掉一辆车
    need++;
  }

  // 如果m >= need，当前有的自行车数量足够
  return m >= need;
}

Java算法源码

import java.util.Arrays;
import java.util.Scanner;

public class Main {
  public static void main(String[] args) {
    Scanner sc = new Scanner(System.in);

    int m = Integer.parseInt(sc.nextLine());
    int[] requirements =
        Arrays.stream(sc.nextLine().split(" ")).mapToInt(Integer::parseInt).toArray();

    System.out.println(getResult(m, requirements));
  }

  public static long getResult(int m, int[] requirements) {
    Arrays.sort(requirements);

    int n = requirements.length;

    // 每辆自行车的限重 至少是 最重的那个人的体重
    long min = requirements[n - 1];
    // 每辆自行车的限重 至多是 最重的和次重的那两个的体重
    long max = requirements[n - 2] + requirements[n - 1];

    long ans = max;

    // 二分取中间值
    while (min <= max) {
      long mid = (min + max) >> 1; // 需要注意的是，min，max单独看都不超过int，但是二者相加会超过int，因此需要用long类型

      if (check(mid, m, requirements)) {
        // 如果mid限重，可以满足m辆车带走n个人，则mid就是一个可能解，但不一定是最优解
        ans = mid;
        // 继续尝试更小的限重，即缩小右边界
        max = mid - 1;
      } else {
        // 如果mid限重，不能满足m辆车带走n个人，则mid限重小了，我们应该尝试更大的限重，即扩大左边界
        min = mid + 1;
      }
    }

    return ans;
  }

  /**
   * @param limit 每辆自行车的限重
   * @param m m辆自行车
   * @param requirements n个人的体重数组
   * @return m辆自行车，每辆限重limit的情况下，能否带走n个人
   */
  public static boolean check(long limit, int m, int[] requirements) {
    int l = 0; // 指向体重最轻的人
    int r = requirements.length - 1; // 指向体重最重的人

    // 需要的自行车数量
    int need = 0;

    while (l <= r) {
      // 如果最轻的人和最重的人可以共享一辆车，则l++,r--，
      // 否则最重的人只能单独坐一辆车，即仅r--
      if (requirements[l] + requirements[r] <= limit) {
        l++;
      }
      r--;
      // 用掉一辆车
      need++;
    }

    // 如果m >= need，当前有的自行车数量足够
    return m >= need;
  }
}

Python算法源码

# 输入获取
m = int(input())
requirements = list(map(int, input().split()))


def check(limit):
    """
    :param limit: 每辆自行车的限重
    :return: m辆自行车，每辆限重limit的情况下，能否带走n个人
    """
    l = 0  # 指向体重最轻的人
    r = len(requirements) - 1  # 指向体重最重的人

    # 需要的自行车数量
    need = 0

    while l <= r:
        # 如果最轻的人和最重的人可以共享一辆车，则l++,r--，
        # 否则最重的人只能单独坐一辆车，即仅r--
        if requirements[l] + requirements[r] <= limit:
            l += 1
        r -= 1
        # 用掉一辆车
        need += 1

    # 如果m >= need，当前有的自行车数量足够
    return m >= need


def getResult():
    requirements.sort()

    # 每辆自行车的限重 至少是 最重的那个人的体重
    low = requirements[-1]
    # 每辆自行车的限重 至多是 最重的和次重的那两个的体重
    high = requirements[-2] + requirements[-1]

    ans = high

    # 二分取中间值
    while low <= high:
        mid = (low + high) >> 1

        if check(mid):
            # 如果mid限重，可以满足m辆车带走n个人，则mid就是一个可能解，但不一定是最优解
            ans = mid
            # 继续尝试更小的限重，即缩小右边界
            high = mid - 1
        else:
            # 如果mid限重，不能满足m辆车带走n个人，则mid限重小了，我们应该尝试更大的限重，即扩大左边界
            low = mid + 1

    return ans


# 算法调用
print(getResult())

C算法源码

#include <stdio.h>
#include <stdlib.h>

#define MAX_SIZE 10000

/*!
 *
 * @param limit 每辆自行车的限重
 * @param m m辆自行车
 * @param requirements n个人的体重数组
 * @param requirements_size n个人
 * @return m辆自行车，每辆限重limit的情况下，能否带走n个人
 */
int check(long long limit, int m, const int requirements[], int requirements_size) {
    int l = 0; // 指向体重最轻的人
    int r = requirements_size - 1;  // 指向体重最重的人

    // 需要的自行车数量
    int need = 0;
    while (l <= r) {
        // 如果最轻的人和最重的人可以共享一辆车，则l++,r--，
        // 否则最重的人只能单独坐一辆车，即仅r--
        if (requirements[l] + requirements[r] <= limit) {
            l++;
        }
        r--;
        // 用掉一辆车
        need++;
    }

    // 如果m >= need，当前有的自行车数量足够
    return m >= need;
}

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

long long getResult(int m, int requirements[], int requirements_size) {
    qsort(requirements, requirements_size, sizeof(int), cmp);

    // 每辆自行车的限重 至少是 最重的那个人的体重
    long long min = requirements[requirements_size - 1];
    // 每辆自行车的限重 至多是 最重的和次重的那两个的体重
    long long max = requirements[requirements_size - 2] + requirements[requirements_size - 1];

    long long ans = max;

    // 二分取中间值
    while (min <= max) {
        long long mid = (min + max) >> 1; // 需要注意的是，min，max单独看都不超过int，但是二者相加会超过int，因此需要用long long类型

        if (check(mid, m, requirements, requirements_size)) {
            // 如果mid限重，可以满足m辆车带走n个人，则mid就是一个可能解，但不一定是最优解
            ans = mid;
            // 继续尝试更小的限重，即缩小右边界
            max = mid - 1;
        } else {
            // 如果mid限重，不能满足m辆车带走n个人，则mid限重小了，我们应该尝试更大的限重，即扩大左边界
            min = mid + 1;
        }
    }

    return ans;
}

int main() {
    int m;
    scanf("%d", &m);

    int requirements[MAX_SIZE];
    int requirements_size = 0;

    while (scanf("%d", &requirements[requirements_size++])) {
        if (getchar() != ' ') break;
    }

    printf("%lldn", getResult(m, requirements, requirements_size));

    return 0;
}