独木舟

一群人去旅行要租用独木舟，每艘独木舟最多乘两人，且所有独木舟有一个统一的载重限度。

给出独木舟的载重限度和每个人的体重，现求最少需要租用多少独木舟。

输入

第一行一个整数 w，表示独木舟的载重量。（80 ≤ w ≤ 200）

第二行一个整数 n，表示旅游人数。 （1 ≤ n ≤ 30000）

接下来 n 行，每行一个数表示 ai，即每个人的重量 （5 ≤ ai ≤ w）

输出

接下来 n 行，每行一个数表示 ai，即每个人的重量 （5 ≤ ai ≤ w）

样例：

1
2
3
4
5
6
7
8
9
10
11
100
9
90
20
20
30
50
60
70
80
90
1
6

参考代码

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
#include<iostream>
#include<algorithm>
using namespace std;

int weight[30005];

int main() {
	//1.数据录入
	int w;//独木舟载重量
	int n;//旅游的人数
	cin >> w >> n;
	for (int i = 0; i < n; ++i) cin >> weight[i];
	sort(weight, weight + n);
	//2.进行数据处理
	int count = 0;
	if (weight[0] * 2 > w) {//特殊情况处理
		count = n;
	} else {//一般情况处理
		for (int i = 0; i < n; ++i) {
			for (int j = n - 1; j >= 0; --j) {
				if (weight[j] == 0) continue;
				if ((weight[i] + weight[j]) <= w || i == j) {
					count++;
					weight[j] = 0;
					weight[i] = 0;
					break;
				}
			}
		}
	}
	cout << count << endl;
	return 0;
}