P1028 过河问题
2024-10-08 03:52:07
题目描述
为了躲避黑暗大魔王的追杀,zifeiy与他的伙伴们共N人连夜逃出了黑暗城堡,他们走到一条河的东岸边,想要过河到西岸。而东岸边有一条小船。
船太小了,一次只能乘坐两人。每个人都有一个渡河时间T,船划到对岸的时间等于船上渡河时间较长的人所用时间。
现在已知N个人的渡河时间T,zifeiy想要你告诉他,他们最少要花费多少时间,才能使所有人都过河。
注意,只有船在东岸(西岸)的人才能坐上船划到对岸。
输入格式
输入文件第一行为人数N,以下有N行,每行一个数。
第i+1行的数为第i个人的渡河时间。
输出格式
输出一个整数,表示所有人都渡过河的最少渡河时间
样例输入
4
6
7
10
15
样例输出
42
提示
[数据范围]
对于40%的数据满足N≤8。
对于100%的数据满足N≤100000。
[样例解释]
初始:东岸{1,2,3,4},西岸{}
第一次:东岸{3,4},西岸{1,2} 时间7 第二次:东岸{1,3,4},西岸{2} 时间6 第三次:东岸{1},西岸{2,3,4},时间15 第四次:东岸{1,2},西岸{3,4} 时间7 第五次:东岸{},西岸{1,2,3,4} 时间7
所以总时间为7+6+15+7+7=42,没有比这个更优的方案。
最新文章
- [Java面经] 关于面试的二三事.
- windows 常用命令
- WPF学习之路(七)应用程序和窗口
- Inheritance
- JavaSE GUI显示列表 JTable的刷新 重新加载新的数据
- cglib源码分析(三):Class生成策略
- QT美化界面的文章(真的很美)
- 【C语言探索之旅】 第一部分第七课:循环语句
- Java面试题:写代码使得分别出现StackOverflowError和OutOfMemoryError
- Linux - 简明Shell编程09 - 重定向(Redirection)
- Oracle tablespace 创建表空间
- 《The book of shaders》读书笔记
- 算法练习,链表二分最大n个
- activemq 控制面板里的 Number Of Pending Messages、 Messages Enqueued、Messages Dequeued含
- 基于HTML5功能强大的滑块幻灯片
- spring boot入门笔记 (一) - 一个简单的说明+一个案例
- JAVA多线程提高五:原子性操作类的应用
- BZOJ4198 &; 洛谷2168 &; UOJ130:[NOI2015]荷马史诗——题解
- 【BZOJ4711】小奇挖矿 树形DP
- spark源码阅读之network(2)
热门文章
- uml设计之多重性
- input的相关兼容性问题
- 【python小随笔】单例模式设计(易懂版)
- [idea]idea配置tomcat 标签: tomcatidea 2017-03-12 22:12 402人阅读 评论(19)
- Black-White-Blocks
- php的一些误解
- AGC029 E: Wandering TKHS
- hdu1532&;&;poj1273 最大流
- form表单提交,后台怎么获取select的值?后台直接获取即可,和input方式一样。
- 胡喜:从 BASIC 到 basic ,蚂蚁金服技术要解决两个基本的计算问题