返回目录

题目描述

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

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

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

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

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

输入描述

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

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

输出描述

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

示例：

题目解析

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

Python算法源码

def check(limit, m, requirements):
    l = 0  # 指向体重最轻的人
    r = len(requirements) - 1  # 指向体重最重的人
    need = 0  # 需要的自行车数量

    while l <= r:
        if requirements[l] + requirements[r] <= limit:
            l += 1
        r -= 1
        need += 1

    return m >= need

def get_result(m, requirements):
    requirements.sort()
    n = len(requirements)
    min_weight = requirements[n - 1]  # 每辆自行车的限重 至少是 最重的那个人的体重
    max_weight = requirements[n - 2] + requirements[n - 1]  # 每辆自行车的限重 至多是 最重的和次重的那两个的体重
    ans = max_weight  # 初始化结果为最大限重

    while min_weight <= max_weight:
        mid = (min_weight + max_weight) // 2  # 二分取中间值

        if check(mid, m, requirements):
            ans = mid  # 如果mid限重可以满足条件，则更新结果
            max_weight = mid - 1  # 缩小右边界
        else:
            min_weight = mid + 1  # 扩大左边界

    return ans

def main():
    m = int(input())
    requirements = list(map(int, input().split()))
    print(get_result(m, requirements))

if __name__ == "__main__":
    main()

C算法源码

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

#define MAX_SIZE 10000

int m;
int requirements[MAX_SIZE];

int check(long long limit, int n) {
    int l = 0; // 指向体重最轻的人
    int r = n - 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 n) {
    qsort(requirements, n, sizeof(int), cmp);

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

    long long ans = high;

    // 二分取中间值
    while (low <= high) {
        long long mid = (low + high) >> 1;

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

    return ans;
}

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

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

    printf("%lld\n", getResult(n));

    return 0;
}

Java算法源码

import java.util.*;

public class Main {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int m = scanner.nextInt();
        scanner.nextLine(); // 消耗换行符
        String[] requirementsInput = scanner.nextLine().split(" ");
        int[] requirements = new int[requirementsInput.length];
        for (int i = 0; i < requirementsInput.length; i++) {
            requirements[i] = Integer.parseInt(requirementsInput[i]);
        }
        System.out.println(getResult(m, requirements));
    }

    // 获取结果函数
    public static int getResult(int m, int[] requirements) {
        Arrays.sort(requirements); // 对体重进行排序
        int n = requirements.length;

        // 计算每辆自行车的限重范围
        int min = requirements[n - 1];
        int max = requirements[n - 2] + requirements[n - 1];
        int ans = max;

        // 二分查找可能的解
        while (min <= max) {
            int mid = (min + max) / 2;
            if (check(mid, m, requirements)) {
                ans = mid;
                max = mid - 1;
            } else {
                min = mid + 1;
            }
        }

        return ans;
    }

    // 检查函数，判断给定限重下是否满足条件
    public static boolean check(int 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;
    }
}