51nod_learn_greedy_独木舟问题

n个人,已知每个人体重。独木舟承重固定,每只独木舟最多坐两个人,可以坐一个人或者两个人。显然要求总重量不超过独木舟承重,假设每个人体重也不超过独木舟承重,问最少需要几只独木舟?

输入
输出
 
 
输入示例
输出示例
 
贪心的策略是…尽可能让多的船载两个人…
我们可以先排序…
然后从两边取.
如果当前最大的能和最小的一起走,就一起走
不能的话就自己走…
然后直到所有人走完

View Code

 

作者: CrazyKK

ex-ACMer@hust,researcher@sensetime

说点什么

您将是第一位评论人!

提醒
wpDiscuz