首页
Python
Java
前端
数据库
Linux
Chatgpt专题
开发者工具箱
乘船专题
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
阅读更多...