zhege122 @ 2024-11-16 13:14:37

#include <bits/stdc++.h>

using namespace std;

const int N = 1e5 + 10;
int a[N];

int main() {
    int t;
    scanf("%d", &t);
    while (t--) {
        int n;
        long long m;
        scanf("%d%lld", &n, &m);
        long long sum = 0;
        for (int i = 1; i <= n; i++) {
            scanf("%d", &a[i]);
            sum += a[i];
        }
        if ((m - sum) % n == 0 || (sum - m) % n == 0) {
            printf("0\n");
        } else {
            sort(a+1, a+n+1);
            // 从这里就不会写了~ 
        }
    }

    return 0;
}

by Yzmddsw @ 2024-11-16 13:33:31

@zhege122 显然可以考虑二分

by zhege122 @ 2024-11-16 13:45:35

@Yzmddsw

#include <bits/stdc++.h>

using namespace std;

bool check(vector<long long>& wealth, long long m, long long maxDiff, long long& totalSum) {
    long long n = wealth.size();
    sort(wealth.rbegin(), wealth.rend());
    vector<long long> prefixSum(n + 1, 0);
    for (long long i = 0; i < n; i++) {
        prefixSum[i+1] = prefixSum[i] + wealth[i];
    }
    for (long long i = 0; i < n; i++) {
        long long numPeople = i + 1;
        long long neededSum = (wealth[i] - maxDiff) * numPeople;
        if (prefixSum[n] - neededSum >= m) {
            totalSum = prefixSum[n] - neededSum - m;
            return true;
        }
    }
    return false;
}

long long solve(long long n, long long m, vector<long long>& wealth) {
    // 二分 
    long long l = 0;
    long long r = 1e9;
    long long ret = 1e9;
    long long tot = 0;
    while (l <= r) {
        long long mid = (l + r) / 2;
        if (check(wealth, m, mid, tot)) {
            ret = mid;
            r = mid - 1;
        } else {
            l = mid + 1;
        }
    }
    return ret;
}

int main() {
    long long T;
    scanf("%lld", &T);
    while (T--) {
        long long n, m;
        scanf("%lld%lld", &n, &m);
        vector<long long> wealth(n);
        for (long long i = 0; i < n; i++) {
            scanf("%lld", &wealth[i]);
        }
        printf("%lld\n", solve(n, m, wealth));
    }

    return 0;
}

一点不对