华为OD 2022Q4 租车骑绿岛

部门组织绿岛骑行团建活动。租用公共双人自行车，每辆自行车最多坐两人，最大载重M。

给出部门每个人的体重，请问最多需要租用多少双人自行车。(应该是最少租用吧?)

输入描述

第一行两个数字m、n，分别代表自行车限重，部门总人数。

第二行，n个数字，代表每个人的体重，体重都小于等于自行车限重m。

• 0<m<=200
• 0<n<=1000000

输出描述

最小需要的双人自行车数量。

用例

题目解析

本题需要最少的车辆，即尽可能组合出重量小于等于m的两人组: 尽量让体重最大和体重最小的那两个人一辆车,先把人按体重从大到小排序,如果体重最大 + 体重最小 大于 自行车载重, 就让体重大的那个人单独一辆车

利用双指针:

例如:

自行车载重: 6

索引: 0 1 2 3 4 5

体重: 6 5 4 3 2 1

left 是 最左边那个人 ,索引 0, 体重 6

right 是 最右边那个人 , 索引 5,体重 1

一次遍历后

自行车载重: 6

索引: 1 2 3 4 5

体重: 5 4 3 2 1

left 是 最左边那个人 ,索引 1, 体重 5

right 是 最右边那个人 , 索引 5,体重 1

再次遍历后

自行车载重: 6

索引: 2 3 4

体重: 4 3 2

left 是 最左边那个人 ,索引 2, 体重 4

right 是 最右边那个人 , 索引 4,体重 2

再次遍历后

自行车载重: 6

索引: 3

体重: 3

此时 left = right = 3,体重为3的这个人单独一辆车

Java源码

import java.util.Collections;
import java.util.List;
import java.util.Scanner;
import java.util.ArrayList;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        String line1 = sc.nextLine();
        String[] strings = line1.split(" ");
        // 自行车载重
        Integer load = Integer.parseInt(strings[0]);
        String line2 = sc.nextLine();
        String[] people = line2.split(" ");
        // 体重列表
        List<Integer> weightList = new ArrayList<>();
        for (int i = 0; i < people.length; i++) {
            weightList.add(Integer.parseInt(people[i]));
        }
        // 将每个人按体重由大到小排序
        Collections.sort(weightList, Collections.reverseOrder());
        // 最左边的人体重,也是最大体重
        int left =0;
        // 最右边的人的体重,也是最小体重
        int right = weightList.size() -1;
        int bikeNum =0;
        while (left < right) {
            Integer maxWeight = weightList.get(left);
            Integer minWeight = weightList.get(right);
            // 最大体重 + 最小体重 <= 自行车载重
            if (minWeight + maxWeight <= load) {
                left ++;
                right --;
                bikeNum ++;
            } else {
                // 体重最大的那个人单独一辆车
                left ++;
                bikeNum ++;

            }
        }
        // 剩下最后一个人,单独一辆车
        if (left == right) {
            bikeNum++;
        }

        System.out.println(bikeNum);
    }
}

JavaScript算法源码

/* JavaScript Node ACM模式 控制台输入获取 */
const readline = require("readline");
 
const rl = readline.createInterface({
  input: process.stdin,
  output: process.stdout,
});
 
const lines = [];
rl.on("line", (line) => {
  lines.push(line);
 
  if (lines.length === 2) {
    const [m, n] = lines[0].split(" ").map(Number);
    const arr = lines[1].split(" ").map(Number);
 
    console.log(getResult(arr, m, n));
 
    lines.length = 0;
  }
});
 
function getResult(arr, m, n) {
  arr.sort((a, b) => a - b);
 
  let count = 0;
 
  // while (arr.at(-1) >= m) {
  //   count++;
  //   arr.pop();
  // }
 
  let i = 0;
  let j = arr.length - 1;
 
  while (i < j) {
    if (arr[i] + arr[j] <= m) i++;
    j--;
    count++;
  }
 
  if (i === j) count++;
 
  return count;
}

Python算法源码

# 输入获取
m, n = map(int, input().split())
arr = list(map(int, input().split()))
 
 
# 算法入口
def getResult(arr, m, n):
    arr.sort()
 
    count = 0
 
    i = 0
    j = n - 1
 
    while i < j:
        if arr[i] + arr[j] <= m:
            i += 1
        j -= 1
        count += 1
 
    if i == j:
        count += 1
 
    return count
 
 
# 算法调用
print(getResult(arr, m, n))