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

Codeforces Round #318 [RussianCodeCup Thanks-Round] (Div. 2) A. Bear and Elections | 书脊
http://codeforces.com/contest/574/problem/A

Limak is a grizzly bear who desires power and adoration. He wants to win in upcoming elections and rule over the Bearland.

There are n candidates, including Limak. We know how many citizens are going to vote for each candidate. Now i-th candidate would get ai votes. Limak is candidate number 1. To win in elections, he must get strictly more votes than any other candidate.

Victory is more important than everything else so Limak decided to cheat. He will steal votes from his opponents by bribing some citizens. To bribe a citizen, Limak must give him or her one candy - citizens are bears and bears like candies. Limak doesn't have many candies and wonders - how many citizens does he have to bribe?

Input

The first line contains single integer n (2 ≤ n ≤ 100) - number of candidates.

The second line contains n space-separated integers a1, a2, ..., an (1 ≤ ai ≤ 1000) - number of votes for each candidate. Limak is candidate number 1.

Note that after bribing number of votes for some candidate might be zero or might be greater than 1000.

Output

Print the minimum number of citizens Limak must bribe to have strictly more votes than any other candidate.

Sample test(s)

input

5
5 1 11 2 8

output

4

input

4
1 8 8 8

output

6

input

2
7 6

output

0

Note

In the first sample Limak has 5 votes. One of the ways to achieve victory is to bribe 4 citizens who want to vote for the third candidate. Then numbers of votes would be 9, 1, 7, 2, 8 (Limak would have 9 votes). Alternatively, Limak could steal only 3votes from the third candidate and 1 vote from the second candidate to get situation 9, 0, 8, 2, 8.

In the second sample Limak will steal 2 votes from each candidate. Situation will be 7, 6, 6, 6.

In the third sample Limak is a winner without bribing any citizen.

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


http://www.cnblogs.com/yspworld/p/4771064.html

将2--n号人的选票数加入到一个大数优先的优先队列。只要1号候选人的票数少于对首人的，就将队首元素取出队列&&值-1， 1号人的+1.计数器+1，再将这个
元素加入到优先队列中。直到1号人的票数>队首元素。

int main() {     int n;     while(scanf("%d", &n)!=EOF)     {         int head;         priority_queue<int, vector<int>, less<int> >q;         scanf("%d", &head);         int cur;         for(int i=2; i<=n; i++){             scanf("%d", &cur); q.push(cur);         }         int ans=0;         while(head<=q.top())         {             cur=q.top(); q.pop();             head++; cur--; ans++;             q.push(cur);         }         printf("%d\n", ans);     }     return 0; }

X.
分析: 这题的做法很多, 我开始的时候暴了一下, 发现过不了, 暴的复杂度是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;

    }

Read full article from Codeforces Round #318 [RussianCodeCup Thanks-Round] (Div. 2) A. Bear and Elections | 书脊