题目描述

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

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

输入描述

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

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

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

输出描述

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

测试样例1

输入

3 4
3 2 2 1

输出

3

Python代码解析

def min_bicycles_needed(m, n, weights):
    # 排序
    weights.sort()

    left = 0  # 最轻的人的指针
    right = n - 1  # 最重的人的指针
    count = 0  # 需要的自行车数量

    while left <= right:
        if weights[left] + weights[right] <= m:
            # 可以配对
            left += 1  # 移动轻的人指针
            right -= 1  # 移动重的人指针
        else:
            # 不能配对，重的人单独乘坐
            right -= 1

        count += 1  # 无论配对与否，都需要一辆自行车

    return count


# 输入处理
m, n = map(int, input().split())
weights = list(map(int, input().split()))

# 输出结果
print(min_bicycles_needed(m, n, weights))