题解：CF2014C Robin Hood in Town

· · 题解

解题思路

  1. 当 n = 1 或者 n = 2 时根据题目条件一定无解。
  2. 将求出 a 数组的和，a 是输入数组并且将其求和记作 cnt。
  3. 因为对 a 从小到大排序所以数组的第 \frac{n}{2}+1 的位置就是中间值。
  4. 用平均值计算出有超过一半的人口感到不幸福时钱有多少最后减去总和也就是 cnt 即可。

给出代码

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N=2e5+5;
int n;
int a[N];
int cnt;
int mid,s,t;
signed main (){
    scanf("%d",&t);
    while(t--){
        scanf("%d",&n);
        cnt=0;//有多组数据初始化
        for(int i=1; i<=n; i++){
            scanf("%d",&a[i]);
            cnt+=a[i];//求和
        }
        if(n==1||n==2){//判断无解情况
            printf("-1\n");
            continue;
        }
        sort(a+1,a+n+1);//排序
        mid=a[(n/2)+1];
        mid=mid*2*n+1;
        printf("%d\n",max(0LL,mid-cnt));
    }
    return 0;
}