当前位置:首页 > 贪心 > 正文
NOI4.6-2469电池的寿命
2731+

题目大意:有n块5好电池,各有各的使用时长,用的时候需要两块一起用,如何搭配,才能使总的使用时间最长?最长使用时间是多久?

题目描述

小S新买了一个掌上游戏机,这个游戏机由两节5号电池供电。为了保证能够长时间玩游戏,他买了很多5号电池,这些电池的生产商不同,质量也有差异,因而使用寿命也有所不同,有的能使用5个小时,有的可能就只能使用3个小时。显然如果他只有两个电池一个能用5小时一个能用3小时,那么他只能玩3个小时的游戏,有一个电池剩下的电量无法使用,但是如果他有更多的电池,就可以更加充分地利用它们,比如他有三个电池分别能用3、3、5小时,他可以先使用两节能用3个小时的电池,使用半个小时后再把其中一个换成能使用5个小时的电池,两个半小时后再把剩下的一节电池换成刚才换下的电池(那个电池还能用2.5个小时),这样总共就可以使用5.5个小时,没有一点浪费。

现在已知电池的数量和电池能够使用的时间,请你找一种方案使得使用时间尽可能的长。

输入

输入包含多组数据。每组数据包括两行,第一行是一个整数N (2 ≤ N ≤ 1000),表示电池的数目,接下来一行是N个正整数表示电池能使用的时间。

输出

对每组数据输出一行,表示电池能使用的时间,保留到小数点后1位。

样例输入

2
3 5
3
3 3 5

样例输出

3.0
5.5

提示

提示:可能有的电池可以用1个小时,或者更长时间。

解题思路

两块电池:小的那块能用多久就用多久。

三块电池:如果最大的那块电池比另外两块电池的时间和还长,答案为另外两块电池的时间和,否则电可以用尽:三块电池按时长从小到大分别编号为1、2、3;2号电池跟3号电池一起用,用到2号电池跟1号电池同等电量;1号和2号电池,分别和3号电池搭配使用,各用3号电池一半电量;最后1号和2号电池一起用完。

三块以上电池:可以转换成三块电池或者两块电池的情况。

转换成三块电池:最长时间不超过总时间一半,可以用尽。如有n(n>3)块电池,可以将其分成3组(每一组分别看成一块电池):电池按时间从小到大排序,第一组为前m(m<=n-2)块电池,如果再加入任意一块电池都会超过总时间一半;其余电池随便分成2组。这样,任意两组加起来都会超过总电量一半。

转换成两块电池:最长时间超过总时间一半,时间最长的单独一组,其余为第二组,答案为第二组时间总和。

综上所述,共有2种情况:最长时间超过总时间一半,能用的时间为其余电池的时间之和;最长时间不超过总时间一半,能用尽所有电,即时间总和除以2。

程序实现

About

坚决不Copy代码!

本文标签:,,

NOI4.6-2469电池的寿命:等您坐沙发呢!

发表评论

您必须 [ 登录 ] 才能发表留言!