题目名称	225. 乘船渡河
输入输出	`kaj.in/out`
难度等级	★
时间限制	1000 ms (1 s)
内存限制	128 MiB
测试数据	10
题目来源	BYVoid 于2008-11-28加入
开放分组	全部用户
提交状态
分类标签	贪心排序
	分享题解

通过：222，提交：452，通过率：49.12%
dateri	100	0.000 s	0.00 MiB	C++
Regnig Etalsnart	100	0.000 s	0.00 MiB	C++
dew52	100	0.000 s	0.00 MiB	C++
lihaoze	100	0.000 s	0.00 MiB	C++
syzhaoss	100	0.000 s	0.00 MiB	C++
┭┮﹏┭┮	100	0.000 s	0.00 MiB	C++
Hyoi_iostream	100	0.000 s	0.04 MiB	C++
Hyoi_0Koto	100	0.000 s	0.29 MiB	C++
521	100	0.001 s	0.04 MiB	C++
西园雪没	100	0.001 s	0.04 MiB	C++

本题关联比赛
假期找点事儿做题吧
板子大赛

关于乘船渡河的近10条评论(全部评论)
学会了快排从大到小，因为数组小了还e了一次，真是水 ShallowDream雨梨 2018-04-02 20:39 11楼
淼淼淼淼淼淼淼 HeHe 2017-07-16 07:10 10楼
贪心，如果目前最重的与最轻的可以在一条船上，就让他在一条船上否则就让最重的独自乘一条船 51nod帮你学 Go灬Fire 2016-10-12 08:13 9楼
忘改文件名了。。。 liu_runda 2016-01-25 12:15 8楼
甘罗 2014-05-28 18:11 7楼
我看到说题目一样，就直接ctrl+c，ctrl+v。结果没有改文件名= = HouJikan 2014-05-18 22:29 6楼
没有用到贪心，不过题真的很水甘罗 2014-04-29 12:53 5楼
这题数据肯定随机很多了。= =堆排优势才发挥的出来啊。 FrCsKOH 2012-11-06 23:54 4楼
很水。。。 11111111 2012-01-02 16:10 3楼
请看：PID:121（纪念品分组），样例数据都一样…… 果然hash排序快啊，完秒随机化快排…… Truth.Cirno 2011-10-28 18:16 2楼

225. 乘船渡河

★ 输入文件：kaj.in 输出文件：kaj.out 简单对比
时间限制：1 s 内存限制：128 MiB

【题目描述】

有 $n$ 个人要乘船过河，其中第 $i$ 个人的重量为 $w_i$。

每艘船的最大载重量为 $c$，且最多只能乘两个人。

问最少需要多少条船可以装下所有人？

【输入格式】

第一行一个整数 $c(80\leq c\leq 200)$，表示船的载重量。

第二行一个整数 $n(n\leq 10000)$，表示总人数。

接下来一行共 $n$ 个整数，其中第 $i$ 个数为第 $i$ 个人的体重 $w_i(w_i\leq c)$。

【输出格式】

一行一个整数，表示最少需要的船只数。

【样例输入】

100
9
90 20 20 30 50 60 70 80 90

【样例输出】

【样例说明】

其中一种乘船方案为 $(90),(20,80),(30,70),(20,50),(60),(90)$，共需要 6 艘船。