想想呃， 定义一个二维数组：A=a[i][j] //n表示第一行输入的正整数-种类数。 //ｉ＝１．．．ｎ,表示第i种品牌电池的寿命。 ｊ＝１．．．ｎ，表示第j种品牌电池的个数。 对A数组第一维排序，然后组合 一次游戏时间的长度为两个电池中最小时间数 大概先想到这些...

哎哟，我好笨。。。

找游戏代练-推荐去【钱庄】 【钱庄】网是中国首家为玩家找代练提供第三方中介担保网。钱庄网不是代练网站而是专业的中介担保网， 已有上百家代练工作室在钱庄网注册，并开通八十余款网络游戏代练担保交易业务，您在这里找代练, 不用找本地的，可以挑最便宜的，并通过钱庄网代练担保交易。安全，快捷（玩家先把钱汇到钱庄网 ， 等代练按时完成了代练任务，玩家验收后，钱庄网才会把钱汇给代练，如果代练没完成，钱庄网就退款给 玩家，代练一分钱也拿不到，再也不用担心，自己的钱汇给骗子代练而受到精神 金钱 时间的损失） 中国网络游戏代练门户网-钱庄 以加入中国诚信企业联盟及诚信公约签名单位 并通过中国网络安全监察及安全站点检测认证 详情请登录【钱庄】网查看 网址 www.qz8888.com

哇塞 发广告 不删啊.. 这个题太麻烦..

似乎没有效率要求啊 这样的话，直接尝试所有电池的Pnn种排列情况不就可以了？ 当然，前两个电池的顺序无关，可以减少一半的情况

没有数据规模吗?小的话dfs,大的话...dp?

不对,貌似直接模拟就能AC

给的输出样例的答案好像不对啊！ 样例给出的电池总个数为六个。 而答案说最少时间为5个小时。 这个结果是怎么得到的啊？ 哪位高手能解释一下。 谢谢！

给的输出样例的答案好像不对啊！ 样例给出的电池总个数为六个。 而答案说最少时间为5个小时。 这个结果是怎么得到的啊？ 哪位高手能解释一下。 谢谢！

给的输出样例的答案好像不对啊！ 样例给出的电池总个数为六个。 而答案说最少时间为5个小时。 这个结果是怎么得到的啊？ 哪位高手能解释一下。 谢谢！

我想题目这个样子解比较合理： 首先，我们要知道一个问题，那就是，什么叫不能继续用了？原因只有一个，只有一个电池有电了。 然后，针对这个题目，我们来假设最后剩余的电池为M小时（也就是还可以用M小时），那么M最大时，为题目最短，M最小时，最长 最后解题，使得M=0....X,假设用了N小时，那么就有 2×N+M=ALL 现在的关键就是对于一个M能否得到一个整数N. 能否得到整数N，这个问题的解答如下： 这个部分的解答因为没有认真考虑，应该有更加快速的方法的。我的方法如下： 在上边部分确定了一个M，那么就一个有一个电池的容量可以假设为电池容量（Ai）-M. 那么此时问题变为给定一组电池和电池容量数据，能否将其分为两组，一组为m1,另一组为m2,它们满足： m1个电池的总容量为N，m2个电池的总容量也为N，同时m1+m2=所有电池数目。 后边这个分组，可以用最一般的方法来做，也可以用规划的方法来做，关键时间花费就在这里了。

楼上的要用动态规划？ 问题实质：将电池分为两组，其中使用时间短那组的越长越好 或者说，两组的重合区域越长越好 解决方法：总电池使用时间为Time，期望最好时间Hope=Time/2, 然后使用类似背包算法，将其最优解设定为最接近Hope的解 (差的绝对值最小)，那么这个解为一组，剩余为一组， 即求得最长使用时间。 设电池中最长使用时间的电池其使用时间为Tmax，将上面类似背包 算法的最优解设定为与Hope的差值的绝对值小于但最接近于Tmax， 那么这个解为一组，剩余为一组，并且Tmax对应那块电池最后使用， 即求得最短使用时间。 （另外：题目示例中应该是每块电池只有1块）

感觉蛮简单的啊,降序排列(一块电池看作一个数据),记录2个总时间长度a、b(初始为0),由排序好的数据序列d[]的d[0]开始穷举,if a<=b,a+=d[i];else,b+=d[i];这样最后的min{a,b}就是最长时间了. 最短时间也简单,依然用上面的序列d[].从d[1]按上面方法开始穷举,最后的min{a,b}为最短时间.

真惭愧啊~~我是楼上的,我的算法出现了本质上的错误,接触程序竞赛也就半年,要努力的还太多了... 小弟的言语可能反了不少人胃口,在此道歉!!

不过想想在上面的基础上在两堆里搜出些电池来交换应该还能骗到点分

CHANG

这个题目不难

贪婪算法 hi.baidu.com/china,欢迎大家来我的空间交流linux下虚拟机技术

不要想了,那个样例的答案就有问题,怎么这么久还没有改! 最长时间16小时呀,如果电池数为双数,最长最小时间就是一样的!

简单的贪婪算法每步尽可能剩余更多/更少的电量,按照样例已经求解不出最小值了 这个题目可以用GA求解,不过能不能得出最小值就得看运气以及允许多长时间了

13楼的思路可行的 我就按照那个做了.. 当达到最大可用时间和最小可用时间时，剩下的有电的电池数都只有一节。那么，剩的这节电池里所剩的电量越大，可用时间就越小，反之。 这样我们就可以简单地求，什么时候剩下的电量最小，让总的电池总电量减去最小的剩下的电量再除于2（每个手柄用两节电池）就可以得到最大可用时间了（这里电量的单位按小时算）。其实求什么时候能剩下最小的电量才是关键。 要剩下的电量最小，那么单节电量最大的电池肯定要用完，防止最后剩下个电量最大的电池。最简单的方法就是先用大电量的电池。所以我们先要对输入的N种电池按电量排序。之后从大电量的电池取，直到取完所有电池。我们只要总电量和剩下的电量。所以在取的过程中，我用一个变量zong储存总电量，用变量yu储存剩下的电量，当yu大于0的时候，yu减去目前取的电池的电量，yu小于0的时候，yu加上目前取的电量。到最后yu是一个小于等于最大电量电池的电量。让zong减去yu再除于2就可以了....... 具体我空间写了写 http://hi.baidu.com/gushaoying/blog/item/abcd318b6e3d4616c9fc7a6a.html

小弟是新手，刚接触竞赛题，但是我感觉楼上说的不对。要求使用时间最短不能从最大的电池开始用，我自己做了几个测试用例都试了，应该剩余的是最大电量的电池，才能使使用时间最短。

关注百度之星~~~~~~~~！

★︵＿＿＿︵☆ ／　　　　　＼ ︴●　　　●　︴永　遠　支　持　你　→≧﹏≠ ︴≡　﹏　≡　︴有　空　幫　你　灌　灌　水　～ ＼＿＿＿＿＿／ 鼓　鼓　掌　～～加　油！ ╭等你╮╭回访╮╭沏茶╮╭等候╮ ╰～～╯╰～～╯╰～～╯╰～～╯

呵呵，复赛的衣服终于都寄出去了，哇咔咔，请大家注意查收噢

★︵＿＿＿︵☆ ／　　　　　＼ ︴●　　　●　︴永　遠　支　持　你　→≧﹏≠ ︴≡　﹏　≡　︴有　空　幫　你　灌　灌　水　～ ＼＿＿＿＿＿／ 鼓　鼓　掌　～～加　油！

睬下

★︵＿＿＿︵☆ ／　　　　　＼ ︴●　　　●　︴永　遠　支　持　你　→≧﹏≠ ︴≡　﹏　≡　︴有　空　幫　你　灌　灌　水　～ ＼＿＿＿＿＿／ 鼓　鼓　掌　～～加　油！

我爱Wii游戏！

我也开始WII啦！