[题解]Codeforces Round #519

【题目】

【描述】

Awruk和Elodreip参加选举，n个人投票，每个人有k张票，第i个人投a[i]张票给Elodreip，投k-a[i]张票给Awruk。求最小的k，使得Awruk比Elodreip得票多。

数据范围：1<=n<=100，1<=a[i]<=100

【思路】

Awruk得票数为n*k-(a[1]+...+a[n])，Elodreip得票数为a[1]+...+a[n]。n*k-(a[1]+...+a[n])>a[1]+...+a[n]推出n*k-(a[1]+...+a[n])>=a[1]+...+a[n]+1推出k>=(2*(a[1]+...+a[n])+1)/n，注意要上取整。

注意：每个人的总票数k要不少于每个人投给Elodreip的票数，即k>=max{a[i]}。

【我的实现】

复杂度：O(n)

 1 #include <iostream>
 2 #include <cstdio>
 3 #include <algorithm>
 4 #include <cstring>
 5 
 6 using namespace std;
 7 
 8 int main()
 9 {
10     int n, k;
11     int x;
12     int sum = 0;
13     int Max_x;
14     scanf("%d", &n);
15     for(int i = 1; i <= n; i++)
16     {
17         scanf("%d", &x);
18         sum += x;
19         if(i == 1)
20             Max_x = x;
21         else
22             Max_x = max(Max_x, x);
23     }
24     k = (2 * sum + 1) / n;
25     if((2*sum+1)%n)
26         k++;
27     k = max(k, Max_x);
28     printf("%d
", k);
29     return 0;
30 }

View Code

【评测结果】