乘船专题

ACM:贪心法:乘船问题。

题目:有n个人,第i个人的重量为wi,每艘船的最大载重量均为C,且最多只能乘两个人。用最少的船装载所有人。 分析:贪心法!            考虑最轻的人i,他应该和谁一起坐呢?如果每个人都无法和他一起坐船,那么唯一的方案就是每个人坐一艘船!            否则,他应该选择能和他一起坐船的人中最重的一个j。            这样的方法是贪心的!因为:它只是让“眼前”的浪费

8.8 乘船问题 以及 贪心策略思路总结

乘船问题: 即,对每个人的重量进行从小到大排序,(从两端分别进行组合,左端指针s,右端指针e) 每次选择重量最大和最轻的两个人一起乘船s++ e-- 船数+1,还需过河的人数-2    如果超重,则重量最大的人单独一艘船 e--,船数+1,还需过河的人数-1 代码: import java.util.Arrays;import java.util.Scanner;public c