Codeforces 574 A. Bear and Elections

简介:

cilck here ~~

                                      ***A. Bear and Elections***


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.

题目大意:就是怎么让第一个数比后面的数都大(做最少的改变)

样例解释:
Input :
5
5 1 11 2 8

Output:
4

第一次:5+1=6   1    11-1=10   2    8
第二次:6+1=7   1    10-1=9    2    8
第三次:7+1=8   1    9-1=8     2    8
第四次:8+1=9   1    8-1=7     2    8

解题思路:通过样例解释来看,只需要每次找最大的数就行,找到就减一,第一个数加一,直到第一个数最大,

上代码:

/*
2015 - 8 - 31 晚上
Author: ITAK

今日的我要超越昨日的我,明日的我要胜过今日的我,
以创作出更好的代码为目标,不断地超越自己。
*/
#include <iostream>

using namespace std;
int arr[105];
int main()
{
    int m;
    while(cin>>m)
    {
        for(int i=0; i<m; i++)
            cin>>arr[i];
        bool flag = 1;
        int ans = 0;
        while(flag)
        {
            flag = 0;
            int Max = -9999999;
            int k = 1;
            for(int i=1; i<m; i++)
            {
                if(arr[i] > Max)
                {
                    Max = arr[i];
                    k = i;
                }
            }
            if(Max >= arr[0])
            {
                arr[k]--;
                arr[0]++;
                ans++;
                flag = 1;
            }
            else
                flag = 0;
        }
        cout<<ans<<endl;
    }
    return 0;
}
/**
input
5
5 1 11 2 8

output
4


input
4
1 8 8 8

output
6


input
2
7 6

output
0
**/
目录
相关文章
codeforces 322 B Ciel and Flowers
有红绿蓝三种颜色的画,每种拿三朵可以组成一束花,或者各拿一朵组成花束,告诉你每种花的数目,求出可能组成最多的花束。 如果你的代码过不了,考虑一下 8 8 9这种组合。 因为数据量很大,我的思想就是局部和总体采用不同的策略。
47 0
codeforces 322 A Ciel and Dancing
有n个男孩和m个女孩,他们要结对跳舞,每对要有一个女孩和一个男孩,而且其中一个要求之前没有和其他人结对,求出最大可以结多少对。
35 0
|
C++
codeforces 305 C. Ivan and Powers of Two
我的思路是这样的,由2^a+2^a = 2^(a+1)可知,如果有两个连续的数a,我们可以把他们合并为a+1放入集合中,使集合中没有重复的数,我可以用stl里的set。如果想要满足题目中的要求,集合中必须有最大那个数个元素,缺多少就可以计算出来了。
29 0
CodeForces 1195C Basketball Exercise (线性DP)
CodeForces 1195C Basketball Exercise (线性DP)
119 0
Codeforces 833E Caramel Clouds
E. Caramel Clouds time limit per test:3 seconds memory limit per test:256 megabytes input:standard input output:standard out...
1161 0
|
人工智能
Codeforces 719B Anatoly and Cockroaches
B. Anatoly and Cockroaches time limit per test:1 second memory limit per test:256 megabytes input:standard input output:stan...
890 0