Codeforces Round #318 [RussianCodeCup Thanks-Round] (Div. 2) A. Bear and Elections

原题: http://codeforces.com/contest/574/problem/A

---

题目大意: 给一个n的数的数组, 问如何让第一个数拿最少数组中别的数字的数,使得第一个数变成这个数组最大的数.

---

分析: 这题的做法很多, 我开始的时候暴了一下, 发现过不了, 暴的复杂度是O(n2), 看来能有lgn的做法. 后来想想, 假设第一个数是数组中最大的数, 那么就可以不用拿别的数, 如果第一个数不是数组中最大的数, 那么它最多拿的数, 应该是数组中最大的数. 假设数组: 5 1 11 2 8. 第一个数5不是数组中最大的数字, 那么我们可以假设, 最坏情况下, 我们最多拿11(11为数组中最大的数字), 使得5变成数组中最大的数字, 当然这个情况是最坏情况.

其次, 上面例子中的5 1 11 2 8的结果是4, 那么我们可以证明, 任何大于4的数字都是可以的. 因此, 我们可以通过二分搜索的办法, 搜索这个数字. 复杂度是o(nlgn), n是每次检查搜索结果的正确性, lg是二分.

public void solve(int testNumber, InputReader in, OutputWriter out) {
        int n = in.readInt();
        int[] ary = IOUtils.readIntArray(in, n);
        int max = Integer.MIN_VALUE;
        for (int i = 0; i < n; i++) {
            if (ary[i] > max)
                max = ary[i];
        }
        int start = 0;
        int end = max;
        while (start <= end) {
            int mid = (start + end) / 2;
            if (check(mid, ary))
                end = mid - 1;
            else
                start = mid + 1;
        }
        out.print(start);
    }
    public boolean check (int g, int[] ary) {
        int diff = 0;
        for (int i = 1; i < ary.length; i++) {
            if (ary[i] >= ary[0]+g){
                diff += ary[i] - (ary[0]+g) + 1;
            }
        }
        return diff <= g;
    }