题解

题面描述

部门组织绿岛骑行团建活动。活动中需要租用公共双人自行车，每辆自行车最多可以坐两人，且自行车的最大载重为 $M$。给定部门每个人的体重，求最少需要租用多少辆双人自行车以满足所有人的骑行需求。

思路

为了最小化所需的自行车数量，我们应尽可能将体重较重的人与体重较轻的人配对，使得他们的体重之和不超过自行车的限重 $M$。具体步骤如下：

1. 排序：将所有人的体重从小到大排序。
2. 双指针法：使用两个指针，一个指向体重最轻的人（左指针），一个指向体重最重的人（右指针）。
3. 配对判断：
   • 如果最轻和最重的人的体重之和 $\leq M$，则他们可以共用一辆自行车，左指针右移，右指针左移，所需自行车数量加一。
   • 否则，最重的人只能单独租用一辆自行车，右指针左移，所需自行车数量加一。
4. 重复上述过程，直到所有人都被分配到自行车上。

cpp

#include <bits/stdc++.h>
using namespace std;

int main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    int m, n;
    cin >> m >> n;
    vector<int> weights(n);
    for(auto &w: weights) cin >> w;
    // 排序体重
    sort(weights.begin(), weights.end());
    int left = 0, right = n-1;
    int bikes = 0;
    while(left <= right){
        // 如果最轻和最重的人可以配对
        if(weights[left] + weights[right] <= m){
            left++;
        }
        // 无论是否配对，最重的人都需要一辆自行车
        right--;
        bikes++;
    }
    cout << bikes;
}

python

def main():
    import sys
    import sys
    # 读取输入的所有数据
    input = sys.stdin.read().split()
    
    # 第一个数是自行车限重 m，第二个数是部门总人数 n
    m = int(input[0])
    n = int(input[1])
    
    # 如果没有人，则不需要自行车
    if n == 0:
        print(0)
        return
    
    # 读取每个人的体重，并转换为整数列表
    weights = list(map(int, input[2:2+n]))
    
    # 对体重进行升序排序，方便后续双指针配对
    weights.sort()
    
    # 初始化左右指针，left 指向最轻的人，right 指向最重的人
    left, right = 0, n-1
    # 初始化所需自行车数量
    bikes = 0
    
    # 使用双指针方法进行配对
    while left <= right:
        # 如果最轻和最重的人的体重之和不超过限重 m，则可以配对
        if weights[left] + weights[right] <= m:
            # 左指针右移，表示最轻的人已被配对
            left +=1
        # 无论是否配对，最重的人都需要一辆自行车
        right -=1
        # 增加自行车计数
        bikes +=1
    
    # 输出所需的最少自行车数量
    print(bikes)

# 调用主函数
if __name__ == "__main__":
    main()

java

import java.util.*;
import java.io.*;

public class Main {
    public static void main(String[] args) throws IOException{
        // 使用 BufferedReader 进行高效输入
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        
        // 读取第一行并拆分为两个部分：m 和 n
        String[] first = br.readLine().split(" ");
        int m = Integer.parseInt(first[0]); // 自行车限重
        int n = Integer.parseInt(first[1]); // 部门总人数
        
        // 如果没有人，则不需要自行车
        if(n == 0){
            System.out.println(0);
            return;
        }
        
        // 读取第二行的体重数据
        String[] parts = br.readLine().split(" ");
        int[] weights = new int[n];
        for(int i=0;i<n;i++) {
            weights[i] = Integer.parseInt(parts[i]);
        }
        
        // 对体重进行升序排序，方便后续双指针配对
        Arrays.sort(weights);
        
        // 初始化左右指针，left 指向最轻的人，right 指向最重的人
        int left =0, right = n-1;
        // 初始化所需自行车数量
        int bikes =0;
        
        // 使用双指针方法进行配对
        while(left <= right){
            // 如果最轻和最重的人的体重之和不超过限重 m，则可以配对
            if(weights[left] + weights[right] <= m){
                // 左指针右移，表示最轻的人已被配对
                left++;
            }
            // 无论是否配对，最重的人都需要一辆自行车
            right--;
            // 增加自行车计数
            bikes++;
        }
        
        // 输出所需的最少自行车数量
        System.out.println(bikes);
    }
}

题目内容

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

给出部门每个人的体重，请问最少需要租用多少双人自行车。

输入描述

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

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

• $0<m<=200$

• $0<n<=1000000$

输出描述

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

样例1

输入

3 4
3 2 2 1

输出

3