题目内容

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

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

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

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

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

输入描述

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

• $1 ≤ N/2 ≤ M ≤ N ≤ 10000$

• $1 ≤ requirements[i] ≤ 10^9$

输出描述

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

样例1

输入

3
3 5 3 4

输出

6

说明

输入数据两行，

第一行输入数据 $3$ 表示开发时间要求，

第二行输入数据表示需求工作量大小，

输出数据一行，表示部门人力需求。

当选择人力为 $6$ 时， $2$ 个需求量为 $3$ 的工作可以在 $1$ 个月里完成，其他 $2$ 个工作各需要 $1$ 个月完成。可以在 $3$ 个月内完成所有需求。

当选择人力为 $5$ 时， $4$ 个工作各需要 $1$ 个月完成，一共需要 $4$ 个月才能完成所有需求。

因此 $6$ 是部门最小的人力需求。

题解

题面描述

部门在进行需求开发时需要进行人力安排。当前部门需要完成 $N$ 个需求，需求用 $requirements$ 表示，$requirements[i]$ 表示第 $i$ 个需求的工作量大小，单位为人月。这部分需求需要在 $M$ 个月内完成开发。进行人力安排后，每个月的人力是固定的。要求每个月最多有 $2$ 个需求开发，并且每个月需要完成的需求总工作量不能超过部门的人力。

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

思路

本题可以通过二分查找的方法来解决，目的是在满足每个月最多完成两个需求且总工作量不超过部门人力的前提下，找到最小的人力需求。

具体步骤如下：

1. 确定二分查找的范围：

   • 最小人力下限为需求中最大的工作量，因为任何一个需求都必须由一个人力完成。
   • 最大人力上限为所有需求的总和。

2. 二分查找过程：

   • 取中间值作为当前的人力需求，判断是否可以在 $M$ 个月内完成所有需求。
   • 判断方法：
     • 将需求按照工作量从小到大排序。
     • 使用双指针法，一个指向最小的需求，一个指向最大的需求，尝试将这两个需求配对在同一个月内完成。
     • 如果两个需求的总工作量不超过当前人力，则配对完成，移动两个指针。
     • 否则，只完成较大的需求，移动较大需求的指针。
     • 记录所需的总月份数，若总月份数不超过 $M$，则当前人力是可行的，继续在更小的人力范围内查找；否则，需要增加人力。

3. 终止条件：

   • 当二分查找的下界与上界相等时，找到最小的人力需求。

cpp

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

// 函数用于判断在给定人力情况下，是否可以在 M 个月内完成所有需求
bool canComplete(vector<long long> &requirements, int M, long long manpower) {
    int months = 0;
    int i = 0;
    int j = requirements.size() - 1;
    
    // 使用双指针法，从两端开始配对
    while (i <= j) {
        if (requirements[i] + requirements[j] <= manpower) {
            // 如果最小和最大可以配对，移动两个指针
            i++;
            j--;
        }
        else {
            // 否则，只完成最大的需求，移动右指针
            j--;
        }
        // 每次配对或单独完成一个需求，增加一个月
        months++;
    }
    // 判断所需的月份是否在允许范围内
    return months <= M;
}

int main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    
    int M;
    cin >> M;
    vector<long long> requirements;
    long long x;
    while(cin >> x){
        requirements.push_back(x);
    }
    // 排序，从小到大
    sort(requirements.begin(), requirements.end());
    
    // 二分查找的下界为最大需求，上界为所有需求的总和
    long long low = *max_element(requirements.begin(), requirements.end());
    long long high = 0;
    for(auto num : requirements) high += num;
    
    long long result = high;
    while(low <= high){
        long long mid = low + (high - low) / 2;
        if(canComplete(requirements, M, mid)){
            result = mid;
            high = mid -1;
        }
        else{
            low = mid +1;
        }
    }
    cout << result;
}

python

import sys

def can_complete(requirements, M, manpower):
    months = 0
    i = 0
    j = len(requirements) -1
    while i <= j:
        if requirements[i] + requirements[j] <= manpower:
            i +=1
            j -=1
        else:
            j -=1
        months +=1
    return months <= M

def main():
    input = sys.stdin.read().split()
    M = int(input[0])
    requirements = list(map(int, input[1:]))
    requirements.sort()
    low = max(requirements)
    high = sum(requirements)
    result = high
    while low <= high:
        mid = (low + high) //2
        if can_complete(requirements, M, mid):
            result = mid
            high = mid -1
        else:
            low = mid +1
    print(result)

if __name__ == "__main__":
    main()

java

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

public class Main {
    // 判断在给定人力下是否可以在 M 个月内完成
    public static boolean canComplete(long[] requirements, int M, long manpower){
        int months =0;
        int i =0;
        int j = requirements.length -1;
        while(i <= j){
            if(requirements[i] + requirements[j] <= manpower){
                i++;
                j--;
            }
            else{
                j--;
            }
            months++;
        }
        return months <= M;
    }
    
    public static void main(String[] args) throws IOException{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String line;
        // 读取 M
        line = br.readLine();
        int M = Integer.parseInt(line.trim());
        // 读取需求数组
        line = br.readLine();
        String[] parts = line.trim().split("\\s+");
        long[] requirements = new long[parts.length];
        for(int i=0;i<parts.length;i++) requirements[i] = Long.parseLong(parts[i]);
        // 排序
        Arrays.sort(requirements);
        // 二分查找
        long low = requirements[requirements.length -1];
        long high = 0;
        for(long num : requirements) high += num;
        long result = high;
        while(low <= high){
            long mid = low + (high - low)/2;
            if(canComplete(requirements, M, mid)){
                result = mid;
                high = mid -1;
            }
            else{
                low = mid +1;
            }
        }
        System.out.println(result);
    }
}