# 欢迎来到「欧弟算法 - 华为OD全攻略」,收录华为OD题库、面试指南、八股文与学员案例！
# 地址：https://www.odalgo.com
# 华为OD机试刷题网站：https://www.algomooc.com
# 添加微信 278166530 获取华为 OD 笔试真题题库和视频

# 输入最大载重量m，数组长度n
m, n = map(int, input().split())
# 输入数组
nums = list(map(int, input().split()))
# 对数组进行排序，使得轻的人在前面，重的人在后面
nums.sort()
# 初始化答案变量
ans = 0
# 设置头尾相向双指针
left, right = 0, n-1
# 双指针过程，执行while循环
while left <= right:
    # 当前最轻的人和最重的人配对
    # 若没超过最大载重量m，则两个人配对
    if nums[left] + nums[right] <= m:
        left += 1
        right -= 1
        ans += 1
    # 如果超过了最大载重量m，则只有重的人right上车
    else:
        right -= 1
        ans += 1

# 输出结果
print(ans)

Java

import java.util.*;

public class Main {
    public static void main(String[] args) {
        // 输入最大载重量m和数组长度n
        Scanner sc = new Scanner(System.in);
        int m = sc.nextInt();
        int n = sc.nextInt();

        // 输入数组nums
        int[] nums = new int[n];
        for (int i = 0; i < n; i++) {
            nums[i] = sc.nextInt();
        }

        // 对数组进行排序，使得轻的人在前面，重的人在后面
        Arrays.sort(nums);

        // 初始化答案变量
        int ans = 0;

        // 设置头尾相向双指针
        int left = 0, right = n - 1;

        // 双指针过程，执行while循环
        while (left <= right) {
            // 当前最轻的人和最重的人配对
            // 若没超过最大载重量m，则两个人配对
            if (nums[left] + nums[right] <= m) {
                left++;
                right--;
                ans++;
            } 
            // 如果超过了最大载重量m，则只有重的人right上车
            else {
                right--;
                ans++;
            }
        }

        // 输出结果
        System.out.println(ans);
        sc.close();
    }
}

C++

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

int main() {
    // 输入最大载重量m和数组长度n
    int m, n;
    cin >> m >> n;

    // 输入数组nums
    vector<int> nums(n);
    for (int i = 0; i < n; i++) {
        cin >> nums[i];
    }

    // 对数组进行排序，使得轻的人在前面，重的人在后面
    sort(nums.begin(), nums.end());

    // 初始化答案变量
    int ans = 0;

    // 设置头尾相向双指针
    int left = 0, right = n - 1;

    // 双指针过程，执行while循环
    while (left <= right) {
        // 当前最轻的人和最重的人配对
        // 若没超过最大载重量m，则两个人配对
        if (nums[left] + nums[right] <= m) {
            left++;
            right--;
            ans++;
        } 
        // 如果超过了最大载重量m，则只有重的人right上车
        else {
            right--;
            ans++;
        }
    }

    // 输出结果
    cout << ans << endl;

    return 0;
}

C

#include <stdio.h>
#include <stdlib.h>

// 比较函数，用于排序
int compare(const void* a, const void* b) {
    return (*(int*)a - *(int*)b);
}

int main() {
    // 输入最大载重量m和数组长度n
    int m, n;
    scanf("%d %d", &m, &n);

    // 输入数组nums
    int nums[n];
    for (int i = 0; i < n; i++) {
        scanf("%d", &nums[i]);
    }

    // 对数组进行排序，使得轻的人在前面，重的人在后面
    qsort(nums, n, sizeof(int), compare);

    // 初始化答案变量
    int ans = 0;

    // 设置头尾相向双指针
    int left = 0, right = n - 1;

    // 双指针过程，执行while循环
    while (left <= right) {
        // 当前最轻的人和最重的人配对
        // 若没超过最大载重量m，则两个人配对
        if (nums[left] + nums[right] <= m) {
            left++;
            right--;
            ans++;
        } 
        // 如果超过了最大载重量m，则只有重的人right上车
        else {
            right--;
            ans++;
        }
    }

    // 输出结果
    printf("%d\n", ans);
    return 0;
}

Node JavaScript

// 读取输入
const fs = require('fs');
const input = fs.readFileSync(0, 'utf-8').split('\n');

// 输入最大载重量m和数组长度n
const [m, n] = input[0].split(' ').map(Number);

// 输入数组nums
let nums = input[1].split(' ').map(Number);

// 对数组进行排序，使得轻的人在前面，重的人在后面
nums.sort((a, b) => a - b);

// 初始化答案变量
let ans = 0;

// 设置头尾相向双指针
let left = 0, right = n - 1;

// 双指针过程，执行while循环
while (left <= right) {
    // 当前最轻的人和最重的人配对
    // 若没超过最大载重量m，则两个人配对
    if (nums[left] + nums[right] <= m) {
        left++;
        right--;
        ans++;
    } 
    // 如果超过了最大载重量m，则只有重的人right上车
    else {
        right--;
        ans++;
    }
}

// 输出结果
console.log(ans);

Go

package main

import (
        "fmt"
        "sort"
)

func main() {
        // 输入最大载重量m和数组长度n
        var m, n int
        fmt.Scanf("%d %d", &m, &n)

        // 输入数组nums
        nums := make([]int, n)
        for i := 0; i < n; i++ {
                fmt.Scan(&nums[i])
        }

        // 对数组进行排序，使得轻的人在前面，重的人在后面
        sort.Ints(nums)

        // 初始化答案变量
        ans := 0

        // 设置头尾相向双指针
        left, right := 0, n-1

        // 双指针过程，执行while循环
        for left <= right {
                // 当前最轻的人和最重的人配对
                // 若没超过最大载重量m，则两个人配对
                if nums[left] + nums[right] <= m {
                        left++
                        right--
                        ans++
                } else {
                        // 如果超过了最大载重量m，则只有重的人right上车
                        right--
                        ans++
                }
        }

        // 输出结果
        fmt.Println(ans)
}

时空复杂度

时间复杂度：O(NlogN)。双指针过程的时间复杂度为O(N)，排序的时间复杂度为O(NlogN)，取其中的较大值。

空间复杂度：O(1)。除了输入的序列，仅需若干常数变量维护遍历过程。