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

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

输入：

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

输出：

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

样例输入：

样例输出：

3.0
5.5

问题分析：

~~终于来了一道中文题目！~~通过题干我们知道小S希望能够最大化利用这些电池，而每一次使用电池需要同时使用两根，所以我们的目标就是在每次选两个电池的情况下，尽可能不要剩下一根还有电的电池。（如果剩下两根及以上就可以接着使用）

乍一看题目，我们可能会觉得并没有什么好的思路，也不知道该怎样去分拆这些电池。所以我们希望通过计算机的方式来解决这个问题：搜索枚举，遍历所有可能的情况。但是此题并不能这么去解，N最大到1000，以及这个题目中每次用的电量可以任意小（比如选两个电池后只用0.1甚至0.01的电）都在提示这个思路已经失效。

所以这个问题又一次需要人脑来进行分析与讨论了，也就是利用贪心法来解出最优答案。

通过分析第一组样例，我们发现：对于一个给定的电池组，最好的情况下（也就是全部电量耗完）答案应该是Sum/2(Sum：全部电量之和)。然而给出的数据总不如人意，其中最麻烦的就是最大的那个电池（我们记作MaxBattery），我们需要通过小电池的配对组合来尽可能地使得这个最大电池的电量耗光。如果最大的电池电量耗不光，那么答案就是(Sum-最大电池剩余电量)/2=Sum-MaxBattery，那么剩下的所以为了后续方便，我们先将这个电池序列进行排序。

while(scanf("%d",&N)!=EOF){
        cin.get();
        int *Battery=new int[N];
        double Sum=0;
        for(int i=0;i<N;i++){
            scanf("%d",&Battery[i]);
            Sum+=Battery[i];
        }
        cin.get();
        sort(Battery,Battery+N);//从小到大排序
}

接下来我们来看第二组数据。对于3 3 5，题目中给出了一种很巧妙的拆分方式，3和3先使用0.5小时，变成2.5和2.5，之后再分别和5去配对，结果是5.5。（也就是最优情况，电量全部耗完）

当我看到这里时，只觉得题目中的解法妙不可言。~~这是人能想出来的解法？~~ 所以为了更明白一点，我们就再分析一些例子，看看这些例子能不能配成最优情况。

分类一：

对于这三个例子，第一个和第二个不必多说，肯定可以配成最佳情况。但对于第三个就不行了，原因在于：MaxBattery太大了，其余电池全部用上也无法耗光。那么一个自然的分类情况就是，如果MaxBattery>=Sum/2，那么答案就是Sum-MaxBattery。（证明：最大的电池至少会剩下电量，则最优结果最大是，并且存在实现这一结果的电池用法）

分类二：

所以，我们只剩下一种情况，就是MaxBattery<Sum/2，对于3 3 5，它配成了最优情况，那么我们自然产生了一个猜想：是否所有这类情况都是最优的呢？

答案是：Yes。我们知道的一种最直观的最优情况是MaxBattery=Sum/2时，然而此时MaxBattery<Sum/2，在不改变MaxBattery的情况下，我们需要让MaxBattery变成全部的一半，我们只能减少剩余的电池电量，也就是让剩余的电池“内耗”掉Sum-MaxBattery*2。这样答案就一定是Sum/2了。

*证明:

我们用数学归纳法来证明上述分类合理且最优：(注意：题目的答案是耗电量的一半)

当N=2时，当前的电池组一定只满足分类一（MaxBattery>Sum/2），答案一定为Sum-MaxBattery与我们的分类结论一致。

不妨设上述分类对于N=2～N=K-1都成立，现在来考虑N=K的情况。

当N=K时，如果电池组中MaxBattery>=Sum/2，根据分类一的证明，结果是Sum-MaxBattery，如果MaxBattery<Sum/2，我们需要让K-1个较小的电池“内耗”掉Sum-MaxBattery*2。根据归纳假设，设前K-1个较小电池中的最大电池电量为并且，如果，则前K-1个较小电池最大可以耗电，内耗操作合法，如果，则前K-1个较小电池最大可以耗电，内耗操作合法，所以此时答案为Sum/2。

由第二数学归纳法，上述分类结论成立且最优。

基于以上讨论我们得到的代码如下：

#include<iostream>
#include<algorithm>
using namespace std;
int main(){
    int N;
    while(scanf("%d",&N)!=EOF){
        cin.get();
        int *Battery=new int[N];
        double Sum=0;
        for(int i=0;i<N;i++){
            scanf("%d",&Battery[i]);
            Sum+=Battery[i];
        }
        cin.get();
        sort(Battery,Battery+N);//从小到大排序
        double MaxTime;
        if(Battery[N-1]>=Sum/2){
            MaxTime=Sum-Battery[N-1];
        }
        else{
            MaxTime=Sum/2;
        }
        printf("%.1lf\n",MaxTime);
        delete []Battery;
    }
}

最终代码：

其实我们可以看到，对Battery数组进行排序是完全没有必要的，因为我们需要的只是其中最大的那个电池，甚至，连建立Battery数组都是没有必要的。我们只需要记录其中的最大值和总电量即可。

#include<iostream>
#include<algorithm>
using namespace std;
int main(){
    int N;
    while(scanf("%d",&N)!=EOF){
        cin.get();
        int Battery;
        double Sum=0;int MaxBattery=0;
        for(int i=0;i<N;i++){
            scanf("%d",&Battery);
            Sum+=Battery;
            MaxBattery=MaxBattery>Battery?MaxBattery:Battery;
        }
        cin.get();
        if(MaxBattery>=Sum/2){
            printf("%.1lf\n",Sum-MaxBattery);
        }
        else{
            printf("%.1lf\n",Sum/2);
        }
    }
}

总结：

又是一道贪心算法的题目，重点就是怎么思考出这个正确的解法以及最后的证明。希望这篇文章可以为您带来帮助！

码农公寓

电池的寿命

要求：

描述：

输入：

输出：