Distribution money

Distribution money

Accepts: 713

Submissions: 1881

Time Limit: 2000/1000 MS (Java/Others)

Memory Limit: 65536/65536 K (Java/Others)

Problem Description

AFA want to distribution her money to somebody.She divide her money into n same parts.One who want to get the money can get more than one part.But if one man's money is more than the sum of all others'.He shoule be punished.Each one who get a part of money would write down his ID on that part.

Input

There are multiply cases. For each case,there is a single integer n(1<=n<=1000) in first line. In second line,there are n integer a1,a2...an(0<=ai<10000)ai is the the ith man's ID.

Output

Output ID of the man who should be punished. If nobody should be punished,output -1.

Sample Input

3
1 1 2
4
2 1 4 3

Sample Output

1
-1
题意：随意排队领薪金，如果一个人领的超过其他人的总和那么这个人将受到惩罚输出这个人的工号，如果没人领的薪金超过其他人的总和输出-1
总共薪金是n，某个人可能领x，那么其他人的总和就是n-x，如果x>n-x即x>n/2，那么这个人领的薪金就超过其他人输出这个人的工号

#include <iostream>
#include <cstdlib>
#include <cstdio>
#include <algorithm>
#include <vector>
#include <queue>
#include <cmath>
#include <stack>
#include <cstring>

using namespace std;

#define INF 0xfffffff
#define maxn 10005

int main()
{
    int n, x, i, k;
    int cnt[maxn];

    while(scanf("%d", &n) != EOF)
    {
        memset(cnt, 0, sizeof(cnt));
        k = -1;
        for(i = 1; i <= n; i++)
        {
            scanf("%d", &x);
            cnt[x]++;
        }

        for(i = 0;  i<= 10000; i++)
        {
            if(cnt[i] > n/2)
            {
                 k = i;
                 break;
            }
        }
       printf("%d
", k);
    }
    return 0;
}