当前没有测试数据。

问题描述

旅行社计划组织一场独木舟旅行。租用的独木舟都是一样的，最多容纳两人，并且每条独木舟有一个载重限制。为了节约费用，旅行社希望尽可能少地租用独木舟。现在，需要根据每个人的体重，计算出最少需要多少条独木舟。

输入格式

1. 第一行是一个整数 w (80 ≤ w ≤ 200)，表示每条独木舟的最大载重量。
2. 第二行是一个正整数 n (1 ≤ n ≤ 30000)，表示参加旅行的人数。
3. 接下来的 n 行，每行是一个正整数 t_i (5 ≤ t_i ≤ w)，表示每个人的体重。

输出格式

输出一个整数，表示最少需要的独木舟数目。

示例输入：

100
5
90
80
70
60
50

示例输出：

3

说明

• 第 1 条独木舟可以容纳体重 90 和 50 的两人。
• 第 2 条独木舟可以容纳体重 80 和 60 的两人。
• 第 3 条独木舟只能容纳体重为 70 的人。

所以最少需要 3 条独木舟。

解题思路

这个问题可以通过贪心算法来解决：

1. ​先排序​：将所有人的体重从小到大排序。
2. ​双指针法​：
   • 一个指针从最轻的人开始，另一个指针从最重的人开始。
   • 每次尝试将最重的人和最轻的人配对，如果他们的总重量不超过独木舟的最大承载重量 w，则这两个人可以共享一条独木舟。
   • 如果不能配对，则最重的人需要一条独木舟，轻的人继续和下一重的人配对。
3. ​结束条件​：当所有人都被安排到独木舟上时，结束。

复杂度分析

• ​时间复杂度​：排序的时间复杂度为 O(n log n)，双指针遍历的时间复杂度为 O(n)。所以总时间复杂度为 O(n log n)，适合处理 n 达到 30000 的情况。
• ​空间复杂度​：使用了一个大小为 n 的数组存储体重，空间复杂度为 O(n)。