Description

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

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

Input

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

Output

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

Sample Input

2
3 5
3
3 3 5

Sample Output

3.0
5.5

题解

贪心
记电池的最大电量为max, 电量总和为sum
分两种情况：
1. max > sum - max， 显然我们可以一直使用max那根电池，然后剩余的电池都与它进行匹配，此时的最长时间为sum - max
2. max <= sum - max， 则max <= sum / 2，对于这种情况，给出结论：最长使用时间为sum / 2（即所有电池都可以被充分利用），下面给出构造解的方法：把每根电池对应的电量进行编号，并按照从小到大排列，对于排列后的第1 ~ sum号电池，匹配第i号和第i + sum/2号，又因为max <= sum/2， max即是最大的电量，所以i和i + sum/2一定不属于编号相同的一段，这样就构造出了一组两两匹配的解，为sum / 2。

#include<iostream>
#include<cstring>
#include<cstdio>
#include<algorithm>
#include<map>
#include<queue>
#include<sstream>
#include<set>
#include<bitset>
#include<vector>
#include<cmath>
using namespace std;
#define ios ios::sync_with_stdio(false)
const double pi=acos(-1.0);
int dx[]={-1,0,1,0,0},dy[]={0,1,0,-1,0};
typedef long long LL;
typedef pair<LL,LL> PII;
const int INF=0x3f3f3f3f;
const LL IINF=0x3f3f3f3f3f3f3f3f;

const int N=1010;
int a[N];
int n;

int main()
{
    while(~scanf("%d",&n))
    {
        int maxv=0;
        double sum=0;
        for(int i=0;i<n;i++)
        {
            cin>>a[i];
            maxv=max(maxv,a[i]);
            sum+=a[i];
        }

        if(maxv > sum-maxv) printf("%.1f\n",sum-maxv);
        else printf("%.1f\n",sum/2);
    }

    // system("pause");
}