Sengxian's Blog

题目地址

描述

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

分析

我们考虑最大的电池（实为最大电池剩余时间，以下均省略） $M$，如果其余的电池时间和 $S < M$，那么显然至多能使用 $S$ 时间，只需要让最大的电池和剩余的电池轮流使用就可以了。

那么 $S > M$ 又如何呢？一个结论是，答案为 $\frac {S + M} 2$，即所有电池都能被用完，我们来考虑证明。

对于一个电池集合 $B$，最大的电池 $M$，小于等于其余的电池和 $S$，我们称这个集合满足条件 $P$。

结论一：如果电池集合满足条件 $P$，那么所有电池一定能用完。
证明：假设电池从大到小排序为 ，满足 $a_0 \le S$。

首先，如果是电池的和是奇数，那么将最大的电池与次大的电池共用 0.5 小时，用后的电池集合为：（不一定严格排序），我们考虑用后的电池集合是否仍然满足条件 $P$，只需要考虑 $a_2$ 是否满足：

$S$ 越大，就越容易满足条件。当 $S = a_0$ 时，不可能有 3 个数，情况不成立。当 $S = a_0 + 1$ 时：

$a_2 \le a_0$ 是恒成立的，$S = a_0 + 1$ 满足条件，那么对于更大的 $S$ 仍然满足条件，所以变换之后的集合仍然满足条件 $P$。也就是说，如果集合的和为奇数，那么我们一定可以将集合的和变为偶数，而且变换之后的集合仍然满足条件 $P$。

考虑电池集合的和为偶数的情况，如果次大的电池是 $0.5$（最大的电池不可能是 $0.5$），那么显然现在的集合为 $\{1, 0.5, 0.5\}$，因为任何时候都只有不多于 2 个小数位是 $0.5$ 的数，这是可以用完的。否则，我们考虑将最大的电池与次大的电池共用一小时，我们可以证明，剩下的电池仍然满足条件 $P$：剩下的电池集合是 （不一定严格排序），同样我们只需要考虑 $a_2$ 成立的条件：

当 $S = a_0$ 时，没有 3 个数，情况不成立。当 $S = a_0 + 1$ 时：

此时如果 $a_2 = a_0$，就不满足条件，但是根据 $S = a_0 + 1$，此时电池集合必然为 $\{1, 1, 1\}$，和是奇数，这与我们的假设和为偶数是矛盾的，所以对 $S = a_0 + 1$ 的情况仍然是成立的。

也就是说，对于满足条件 $P$ 的电池集合 $B$，我们每次都能够减小电池总量，而且保证之后的电池集合仍然满足条件 $P$，所以一定可以用完。

代码

//  Created by Sengxian on 2016/11/18.
//  Copyright (c) 2016年 Sengxian. All rights reserved.
//  OpenJudge 2469 贪心
#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
inline int readInt() {
    static int n, ch;
    n = 0, ch = getchar();
    while (!isdigit(ch)) ch = getchar();
    while (isdigit(ch)) n = n * 10 + ch - '0', ch = getchar();
    return n;
}

const int MAX_N = 1000 + 3;
int n, a[MAX_N];

int main() {
#ifdef DEBUG
    freopen("test.in", "r", stdin);
#endif
    while (~scanf("%d", &n)) {
        for (int i = 0; i < n; ++i) a[i] = readInt();
        sort(a, a + n);
        int sum = 0;
        for (int i = 0; i < n - 1; ++i) sum += a[i];
        if (a[n - 1] >= sum) printf("%.1lf\n", (double)sum);
        else printf("%.1lf\n", (sum + a[n - 1]) / 2.0);
    }
    return 0;
}