成绩统计 参考代码

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

typedef long long LL;
const int maxn = 100000 + 100;
int n, k;
LL T;
LL num[maxn], sum[maxn], tmp[maxn], sum2[maxn];

bool judge(int n) {
    memcpy(tmp, num, sizeof(num));
    sort(tmp + 1, tmp + 1 + n);
    for (int i = 1; i <= n; ++i) {
        sum[i] = sum[i - 1] + tmp[i];
        sum2[i] = sum2[i - 1] + tmp[i] * tmp[i];
    }
    double mn = 1e100;
    for (int i = k; i <= n; ++i) {
        double avg = (sum[i] - sum[i - k]) / k;
        mn = min(mn, sum2[i] - sum2[i - k] - 2 * avg * (sum[i] - sum[i - k]) + k * avg * avg);
    }
    return mn / k <= T;
}

int main() {
#ifdef ExRoc
    freopen("test.txt", "r", stdin);
#endif
    ios::sync_with_stdio(false);

    cin >> n >> k >> T;
    if (n < k) {
        cout << -1 << endl;
        return 0;
    }
    for (int i = 1; i <= n; ++i) {
        cin >> num[i];
    }
    int low = k - 1;
    int high = n + 1;
    int mid;
    while (high - low > 1) {
        mid = (high + low) >> 1;
        if (judge(mid)) {
            high = mid;
        } else {
            low = mid;
        }
    }
    cout << (high == n + 1 ? -1 : high) << endl;

    return 0;
}