***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
**/