建设部网站网站建设学校

(新卷,100分)- 租车骑绿岛（Java & JS & Python）

题目描述

部门组织绿岛骑行团建活动。租用公共双人自行车，每辆自行车最多坐两人，最大载重M。
给出部门每个人的体重，请问最多需要租用多少双人自行车。

输入描述

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

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

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

输出描述

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

用例

题目解析

本题需要最少的车辆，即尽可能组合出重量小于等于m的两人组。

首先，我们可以将所有人按体重升序，然后将最大体重和m比较，若最大体重大于等于m，则这个人只能一人占一辆车，车数量count++，然后将最大体重弹出，继续将剩下体重中最大的和m比较，逻辑同上，直到最大体重小于m时，停止弹出。

在剩余体重中，我们利用双指针，i指针指向最小体重，j指针指向最大体重，然后组合它们，即arr[i]+arr[j]，和m比较，若小于等于m，则说明这两个人可以共享一辆车，车数量count++，然后i++，j--。如果arr[i]+arr[j]>m，则说明两个人无法共享一辆车，我们只能优先将这里车分配给较大体重的人，此时车数量count++，然后j--。

按上面逻辑移动双指针，最后可能会出现两种情况：

• i > j 此情况下所有人均分配到了车，因此可以直接输出count作为题解
• i === j 此情况下还有一个人未分配到车，因此需要count++，为这个人单独分配一辆车

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; }

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 = sc.nextInt(); int n = sc.nextInt(); int[] arr = new int[n]; for (int i = 0; i < n; i++) { arr[i] = sc.nextInt(); } System.out.println(getResult(arr, m)); } public static int getResult(int[] arr, int m) { Arrays.sort(arr); int count = 0; int i = 0; int 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))