【华为OD-E卷-租车骑绿道 100分(python、java、c++、js、c)】
【华为OD-E卷-租车骑绿道 100分(python、java、c++、js、c)】
题目
部门组织绿岛骑行团建活动。租用公共双人自行车,每辆自行车最多坐两人,最大载重M。
给出部门每个人的体重,请问最多需要租用多少双人自行车
输入描述
- 第一行两个数字m、n,分别代表自行车限重,部门总人数。
第二行,n个数字,代表每个人的体重,体重都小于等于自行车限重m。0<m<=200 0<n<=1000000
输出描述
- 最小需要的双人自行车数量
用例
用例一:
输入:
3 4
3 2 2 1
输出:
3
python解法
- 解题思路:
- 这个问题要求将一组人根据体重分配到自行车上,使得每辆自行车的载重不超过给定的最大重量 max_weight。我们需要尽可能地将更多人分配到自行车上。
具体步骤:
排序:
首先,对所有人的体重进行排序。这样可以方便地用双指针策略来判断是否可以将两个人放在同一辆自行车上。
双指针策略:
初始化两个指针,一个指向体重最轻的人(left),另一个指向体重最重的人(right)。
尝试将最轻和最重的两个人一起分配到一辆自行车。如果这两个人的体重之和不超过 max_weight,则可以将这两个人分配到同一辆车上。此时,left 指针向右移动(代表最轻的人已经分配完),right 指针向左移动(代表最重的人也分配完)。
如果这两个人的体重之和超过了 max_weight,则只能将最重的人单独分配到一辆车上,right 指针向左移动。
重复这个过程,直到所有人都分配上自行车。
结束条件:
当 left 指针超过 right 指针时,说明所有人都已经被分配完自行车。
时间复杂度:
排序操作的时间复杂度是 O(n log n),而双指针扫描的时间复杂度是 O(n)。因此,总的时间复杂度是 O(n log n)。
def calculate_bikes(weights, max_weight, total_people):
# 先对所有人的体重进行排序
weights.sort()
# 初始化指针
left, right = 0, total_people - 1
bikes = 0 # 记录分配的自行车数
# 使用双指针策略进行分配
for _ in range(total_people):
# 如果left指针还没超过right指针,说明还有人未分配
if left <= right:
# 如果当前最轻的人和最重的人的体重和小于等于max_weight,放在同一辆车
if weights[left] + weights[right] <= max_weight:
left += 1 # 最轻的人已经分配好,left指针向右移动
# 不论是否配对成功,最重的人一定需要一辆车
right -= 1 # 最重的人已经分配好,right指针向左移动
bikes += 1 # 增加分配的自行车数量
else:
break # 如果所有人都已经分配完,结束循环
return bikes
# 输入:第一行是最大载重和总人数,第二行是每个人的体重
m, n = map(int, input().split())
weights = list(map(int, input().split()))
# 调用函数并输出结果
print(calculate_bikes(weights, m, n))
java解法
- 解题思路
- 该题目是一个典型的双指针问题,要求将一组体重不等的人根据最大承载重量 m 分配到最少数量的车上。每辆车的承载重量不能超过 m,并且每辆车只能承载两个人。我们的目标是尽可能将每辆车的载重充分利用,从而最小化车的数量。
步骤:
排序:
首先,对所有人的体重进行排序。排序后,我们可以尝试将体重最轻的人和最重的人放在同一辆车上。
双指针策略:
初始化两个指针,i 指向体重最轻的人(从左边开始),j 指向体重最重的人(从右边开始)。
每次尝试将 arr[i](最轻的)和 arr[j](最重的)放在同一辆车上。如果这两个人的体重和小于等于 m,则可以将他们放在同一辆车上,此时将 i 指针向右移动,j 指针向左移动;否则,将最重的人单独分配到一辆车上,j 指针向左移动。
每次分配一辆车时,增加 groups 计数器。
结束条件:
当 i 指针超过 j 指针时,说明所有人已经被分配到车上。
时间复杂度:
排序的时间复杂度是 O(n log n),双指针扫描的时间复杂度是 O(n)。因此,总的时间复杂度是 O(n log n)。
import java.util.*;
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(calculate(arr, m));
}
// 计算需要的最小车数
public static int calculate(int[] arr, int m) {
// 对体重数组进行排序
Arrays.sort(arr);
// 初始化车数计数器
int groups = 0;
// 双指针:i指向最轻的,j指向最重的
for (int i = 0, j = arr.length - 1; i <= j; j--) {
// 如果最轻和最重的两个人可以共享一辆车
if (arr[i] + arr[j] <= m) {
i++; // 最轻的人上车,i指针右移
}
// 无论是否配对,都需要为当前最重的人分配一辆车
groups++; // 增加车数
}
// 返回所需的最小车数
return groups;
}
}
C++解法
- 解题思路
- 这道题目要求将一组人根据体重分配到最少数量的车上,且每辆车的承载重量不能超过给定的最大承载重量 lim。每辆车最多可以承载两个人。我们需要尽可能高效地将人分配到车上,以最小化所需车的数量。
解决思路:
排序:
首先,对所有人的体重进行排序。这样可以利用双指针方法,高效地将最轻和最重的人配对,尽量减少车的数量。
双指针策略:
使用两个指针,l 指向体重最轻的人,r 指向体重最重的人。
每次检查 nums[l] + nums[r] 是否小于或等于 lim,即是否可以将 l 和 r 指向的两个人放在同一辆车上:
如果可以,将这两个人放在同一辆车上,并且分别移动两个指针(l++,r–)。
如果不可以,则只能将最重的人单独分配一辆车,移动 r–。
继续执行这个过程,直到所有人都分配到车上。
结束条件:
当 l 和 r 重合时,说明只剩一个人,该人单独一辆车。
最终返回:
返回分配的车数。
时间复杂度:
排序的时间复杂度是 O(n log n),双指针扫描的时间复杂度是 O(n)。因此,总的时间复杂度是 O(n log n)。
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
// 计算最少车数的函数
int calcRes(vector<int>& nums, int lim) {
// 对体重数组进行排序,方便使用双指针方法
sort(nums.begin(), nums.end());
int cnt = 0; // 记录车数
int l = 0; // 左指针,指向最轻的人
int r = nums.size() - 1; // 右指针,指向最重的人
// 使用双指针算法进行分配
while (l < r) {
// 如果最轻的人和最重的人可以一起坐一辆车
if (nums[l] + nums[r] <= lim) {
l++; // 最轻的人分配一辆车,左指针右移
}
// 最重的人一定需要一辆车,右指针左移
r--;
cnt++; // 增加一辆车
}
// 如果左指针和右指针重合,说明还有一个人未分配
if (l == r) cnt++;
return cnt; // 返回最少车数
}
int main() {
int lim, sz;
cin >> lim >> sz; // 输入最大承载重量和人数
vector<int> nums(sz); // 定义一个数组来存储体重
for (int i = 0; i < sz; i++) {
cin >> nums[i]; // 输入每个人的体重
}
cout << calcRes(nums, lim) << endl; // 输出最少车数
return 0;
}
C解法
首先,对所有人的体重进行排序。排序后,我们可以利用双指针方法,高效地将最轻和最重的人配对,尽量减少车的数量。
双指针策略:
使用两个指针,l 指向体重最轻的人,r 指向体重最重的人。
每次检查 nums[l] + nums[r] 是否小于或等于 lim,即是否可以将 l 和 r 指向的两个人放在同一辆车上:
如果可以,将这两个人放在同一辆车上,并且分别移动两个指针(l++,r–)。
如果不可以,则只能将最重的人单独分配一辆车,移动 r–。
继续执行这个过程,直到所有人都分配到车上。
结束条件:
当 l 和 r 重合时,说明只剩一个人,该人单独一辆车。
最终返回:
返回分配的车数。
时间复杂度:
排序的时间复杂度是 O(n log n),双指针扫描的时间复杂度是 O(n)。因此,总的时间复杂度是 O(n log n)。
#include <stdio.h>
#include <stdlib.h>
// 比较函数,用于qsort排序
int compare(const void* a, const void* b) {
return (*(int*)a - *(int*)b); // 按照升序排序
}
// 计算最少车数的函数
int calcRes(int* nums, int size, int lim) {
// 对体重数组进行排序
qsort(nums, size, sizeof(int), compare);
int cnt = 0; // 记录车数
int l = 0; // 左指针,指向最轻的人
int r = size - 1; // 右指针,指向最重的人
// 使用双指针算法进行分配
while (l < r) {
// 如果最轻的人和最重的人可以一起坐一辆车
if (nums[l] + nums[r] <= lim) {
l++; // 最轻的人分配一辆车,左指针右移
}
// 最重的人一定需要一辆车,右指针左移
r--;
cnt++; // 增加一辆车
}
// 如果左指针和右指针重合,说明还有一个人未分配
if (l == r) cnt++;
return cnt; // 返回最少车数
}
int main() {
int lim, sz;
scanf("%d %d", &lim, &sz); // 输入最大承载重量和人数
int nums[sz]; // 定义一个数组来存储体重
for (int i = 0; i < sz; i++) {
scanf("%d", &nums[i]); // 输入每个人的体重
}
printf("%d\n", calcRes(nums, sz, lim)); // 输出最少车数
return 0;
}
JS解法
更新中
注意:
如果发现代码有用例覆盖不到的情况,欢迎反馈!会在第一时间修正,更新。
解题不易,如对您有帮助,欢迎点赞/收藏