hdu—1002

光頭強選舉

Time Limit: 6000/3000 MS (Java/Others)    Memory Limit: 65536/65536 K (Java/Others)

Total Submission(s): 0    Accepted Submission(s): 0

Problem Description

光頭強非常渴望權利。他想赢得即将到來的選舉。

現在有n個候選人，包括光頭強，其中光頭強是一号候選人。我們現在已經知道每個候選人獲得了多少張選票。其中第i個候選人擁有

ai張選票。為了赢得選舉，光頭強的得票數必須嚴格大于其他候選人。

勝利比一切都重要，是以光頭強決定通過作弊來赢得選舉。他會通過賄賂将給其競争者投票的選民将選票改投給自己。那麼光頭強最少要賄賂幾個選民才能獲得選舉的勝利？

Input

≤ n 

≤ 100)，表示有n個候選人。

接下來1行有n個數 

a1 , 

a2 ,... 

an (1 

≤ai≤ 1000)表示每個候選人的票數。

Output

對于每個測試執行個體，輸出最少要賄賂幾個人才能使光頭強赢得選舉（他的得票數嚴格大于其他所有候選人）

Sample Input

4 
1 8 8 8
5 
5 1 11 2 8      

Sample Output

6
4      

Hint

【分析】

沒什麼好說的...不要想太多就好了,資料範圍給了的隻有100個人，是以每次找票最多的那個人，從他手裡拿一票給自己，直到自己是票數最多的就可以了。

//稍微注意一下題目裡說的是嚴格大于....

【代碼】

#include <stdio.h>
using namespace std;
int n;
int a[110];
int main()
{
    while (~scanf("%d",&n))
    {
        int ma=-1;
        int now=-1;
        for(int i=0;i<n;i++)
        {
            scanf("%d",&a[i]);
            if(a[i]>ma)
            {
                ma=a[i];
                now=i;
            }
        }
        int ans=0;
        while(now!=0)
        {
            a[now]--;
            a[0]++;
            ans++;
            ma=-1;
            for(int i=0;i<n;i++)
                if(a[i]>ma)
                {
                    ma=a[i];
                    now=i;
                }
        }
        for(int i=1;i<n;i++)
            if(a[i]==a[0])
            {
                ans++;
                break;
            }
        printf("%d\n",ans);
    }
    return 0;
}