【华为OD机试真题】租车骑绿道（C++&C&java&python）100%通过率 超详细代码注释 代码深度解读_华为od机试 - 租车骑绿岛

【华为OD机试真题 2022&2023】真题目录 @点这里@

【华为OD机试真题】信号发射和接收 &试读& @点这里@

租车骑绿道

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

输入描述：

第一行两个数字m、n，分别代表自行车限重，部门总人数。
第二行，n个数字，代表每个人的体重，体重都小于等于自行车限重m。

0<m<=200 
0<n<=1000000 
1
2

输出描述：

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

示例1

输入：

3 4
3 2 2 1
1
2

输出：

3
1

解题思路：

1：题目中有两个隐含的条件：

• 一辆车最多骑两个人
• 人的重量不可能大于车的载重

2：那么可以用两个指针，一个指向头部left，一个指向尾部right，如果w【left】+w【right】>车的载重，那么意味着最重的人，加上最轻的人都会超载，只能他一个人骑，right–。
如果w【left】 + w【right】<=车的载重，那么意味着这两个人可以还可以再加人，left ++继续判断直到总重量>车的载重。

C++代码：

代码解读：

代码中首先对人的重量进行排序，从小到大。然后使用左右指针向中间移动的方法，每次选择两个人中最轻的和最重的一起坐船，直到所有人都过河。具体实现中，左指针指向最轻的人，右指针指向最重的人，当前两个人的重量为tempweight。如果tempweight大于m，则右指针向左移动，即选择一个更轻的人；否则，右指针向左移动，即选择一个更轻的人，左指针向右移动，即选择一个更重的人。每次移动后，更新当前两个人的重量。当左指针等于右指针时，说明还有一个人没有被分配到车上，需要再增加一辆车。最后输出最少需要的车的数量。

这种贪心算法的思想是每次选择局部最优解，最终得到全局最优解。时间复杂度为O(nlogn)，主要来自于排序操作。

#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;

int main() {
    // 处理输入
    int m,n;
    cin >> m >> n;
    
    vector<int> weights(n);
    for (int i=0;i<n;i++) {
        cin >> weights[i];
    }
    
    //第一步，排序
    sort(weights.begin(), weights.end()); // 对人的重量进行排序，从小到大
    
    //第二步，左右指针向中间移动
    int left=0; // 左指针指向最轻的人
    int right = n-1; // 右指针指向最重的人
 
    //结果
    int min_bikes = 0; // 最少需要的车的数量
 
    //当前重量
    int temp_weight = weights[right] + weights[left]; // 当前两个人的重量
    
    // 题目中有两个隐含的条件
    // 1: 一辆车最多骑两个人
    // 2：人的重量不可能大于车的载重
    
    for (; left<right; min_bikes++) { // 当左指针小于右指针时，继续循环
        if (temp_weight > m) { // 如果当前两个人的重量大于车的载重
            right --; // 右指针向左移动，即选择一个更轻的人
        } else{
            right --; // 右指针向左移动，即选择一个更轻的人
            left ++; // 左指针向右移动，即选择一个更重的人
        }
        temp_weight = weights[right] + weights[left]; // 更新当前两个人的重量
    }
 
    if (left == right) { // 如果左指针等于右指针，说明还有一个人没有被分配到车上
        min_bikes++; // 需要再增加一辆车
    }
 
    cout << min_bikes << endl; // 输出最少需要的车的数量
    return 0;
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50

C语言代码：

代码解读：

给定的代码是一个解决问题的解决方案，该问题需要找到运输一组人所需的最少自行车数量，给定他们的重量和自行车的最大重量容量。代码首先读取输入值m和n，其中m是自行车的最大重量容量，n是人数。然后它读取每个人的重量并使用冒泡排序算法按升序对它们进行排序。

代码然后将两个指针left和right初始化为已排序的重量数组的第一个和最后一个索引，分别。它还将变量minbikes初始化为0，该变量将跟踪所需的最少自行车数量。然后，代码进入一个循环，直到左指针大于或等于右指针为止。在循环内部，代码检查左指针和右指针处的重量之和是否大于m。如果是，则将右指针递减以选择较轻的人。如果不是，则左右指针都递增和递减，以选择较重和较轻的人。然后计算新左右指针处的重量总和，循环继续。

循环结束后，代码检查左右指针是否相等。如果它们相等，则意味着还有一个人没有被分配到自行车上，因此minbikes会递增。最后，代码打印出minbikes的值。

总体而言，代码正确实现了所需的算法，以找到运输一组人所需的最少自行车数量。用于对重量进行排序的冒泡排序算法不是最有效的排序算法，但对于此问题中使用的小输入大小而言，它是简单且足够的。

#include<stdio.h>

void bubble_sort(int arr[], int n) {
    int i, j, temp;
    for (i = 0; i < n-1; i++) {
        for (j = 0; j < n-i-1; j++) {
            if (arr[j] > arr[j+1]) {
                temp = arr[j];
                arr[j] = arr[j+1];
                arr[j+1] = temp;
            }
        }
    }
}

int main() {
    // 处理输入
    int m,n;
    scanf("%d %d", &m, &n);
    
    int weights[n];
    for (int i=0;i<n;i++) {
        scanf("%d", &weights[i]);
    }
    
    //第一步，排序
    bubble_sort(weights, n); // 对人的重量进行排序，从小到大
    
    //第二步，左右指针向中间移动
    int left=0; // 左指针指向最轻的人
    int right = n-1; // 右指针指向最重的人
 
    //结果
    int min_bikes = 0; // 最少需要的车的数量
 
    //当前重量
    int temp_weight = weights[right] + weights[left]; // 当前两个人的重量
    
    // 题目中有两个隐含的条件
    // 1: 一辆车最多骑两个人
    // 2：人的重量不可能大于车的载重
    
    for (; left<right; min_bikes++) { // 当左指针小于右指针时，继续循环
        if (temp_weight > m) { // 如果当前两个人的重量大于车的载重
            right --; // 右指针向左移动，即选择一个更轻的人
        } else{
            right --; // 右指针向左移动，即选择一个更轻的人
            left ++; // 左指针向右移动，即选择一个更重的人
        }
        temp_weight = weights[right] + weights[left]; // 更新当前两个人的重量
    }
 
    if (left == right) { // 如果左指针等于右指针，说明还有一个人没有被分配到车上
        min_bikes++; // 需要再增加一辆车
    }
 
    printf("%d\n", min_bikes); // 输出最少需要的车的数量
    return 0;
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60

java代码：

解题思路:

对部门人员按照体重进行降序排序。
对人员进行遍历。
如例1:
排序后为 3 2 2 1
1、3等于承重3，则单独辆 count= 1；
2、2 小于3，继续向前找，2+2=4不符合，继续向前找，2+1=3等于3，符合，1已经用过了需要置为0.count+1=2;
3、2 小于3，向前找，只剩刚才处理过的0，遍历结束。结果count+1=3;

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[] weight = new int[n]; // 存储每个人的体重
        for(int i=0; i<n; i++){
            weight[i] = sc.nextInt(); // 输入每个人的体重
        }
        Arrays.sort(weight); // 对体重进行排序，方便安排
        int res = 0; // 记录需要的车的数量
        for(int i = weight.length-1; i>=0; i--){ // 从体重最大的人开始安排
            if(weight[i] == 0){ // 等于0 则代表已经有车了
                continue;
            }
            if(weight[i] == m){ // 一人一辆车
                res ++;
                continue;
            }
            for(int j = i-1; j>=0; j--){ // 从体重次大的人开始安排
                if(weight[j] != 0 && weight[i] + weight[j] <= m){ // 因为已经排过序，遇到合适的就上车
                    weight[j] = 0; // 标记已经有车了
                    break;
                }
            }
            res++; // 记录需要的车的数量
        }
        System.out.println(res); // 输出需要的车的数量
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33

python代码：

代码解读：

代码的主要思路是将人按照重量从小到大排序，然后从最重的人开始往前遍历，每次找到能和他一起骑车的最轻的人，将他们的重量之和标记为0，表示他们已经骑车了。如果最重的人的重量等于车的载重，那么他就独自骑车，不需要找人一起骑车。

# -*- coding = utf-8 -*-
# @Time: 2023/4/5 16:20
# @Author : MR 
# @File : ride_bike.py
# @Software : PyCharm

import sys
# 题目中有两个隐含的条件
#  1: 一辆车最多骑两个人
#  2：人的重量不可能大于车的载重
m, n = map(int, input().split())  # m表示车的载重，n表示人的数量
weight = list(map(int, input().split()))  # 将人的重量存储在一个列表中
weight.sort()  # 将人按照重量从小到大排序
res = 0  # 记录骑车的次数
for i in range(n-1, -1, -1):  # 从最重的人开始往前遍历
    if weight[i] == 0:  # 如果这个人已经骑车了，就跳过
        continue
    if weight[i] == m:  # 如果这个人的重量等于车的载重，他就独自骑车
        res += 1
        continue
    for j in range(i-1, -1, -1):  # 找到能和他一起骑车的最轻的人
        if weight[j] != 0 and weight[i] + weight[j] <= m:  # 如果这个人还没有骑车，并且他们的重量之和不超过车的载重
            weight[j] = 0  # 将他们的重量之和标记为0，表示他们已经骑车了
            break
    res += 1  # 记录需要的车的数量
print(res)  # 输出需要的车的数量
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26