Codeforces Round 974 (Div. 3) C. Robin Hood in Town（排序）

题目链接：题目

大意：

问最大的那个元素要加多少才能使数组中有超过一半的元素小于平均值的一半。

思路：

排序，因为题目涉及中位数，$a[n/2]$就可以获得中位数，如果长度是偶数则获得的是中位数的第二个。然后要使$mid<(sum+x)/2n$，可以移项使得除法换成乘法，这样都可以使用整型计算。实现严格大于的方式就是在等于的情况下加一。
（要注意的是，我一开始在第四个用例wa，后来发现是使用accumulate函数时从0开始累积，导致溢出，改成0LL就行了）

代码：

#include <bits/stdc++.h>
using namespace std;

#define int long long
#define MOD 1000000007
#define fi first
#define se second
#define pii pair<int,int>
#define vec vector

void solve(){
    int n;
    cin >> n;
    vec<int> a(n);
    for(int i = 0; i < n; i++){
        cin >> a[i];
    }
    sort(a.begin(), a.end());
    int sum = accumulate(a.begin(), a.end(), 0ll);
    int mid = a[n / 2];
    if(n <= 2){
        cout << -1 << '\n';
        return;
    }
    if(mid * 2 * n < sum){
        cout << 0 << '\n';
        return;
    }
    cout << mid * 2 * n - sum + 1 << '\n';
}

signed main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    int t=1;
    cin >> t;
    while(t--){
        solve();
    }
    return 0;
}   

原文地址：https://blog.csdn.net/puzhaoyu/article/details/142432408

免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！