提出 #65507230

---

ソースコード 拡げる

#include <bits/stdc++.h>

using namespace std;
 
#define int long long
 
void solve(){    
    int n; cin >> n;

    vector<int> a(n + 1), pre(n + 2), suf(n + 2);
    for(int i = 1; i <= n; i++) cin >> a[i];

    sort(a.begin() + 1, a.end(), greater<int>());

    for(int i = 1; i <= n; i++) pre[i] = pre[i - 1] + a[i];
    for(int i = n; i >= 1; i--) suf[i] = suf[i + 1] + a[i];

    auto get = [&](int i, int j){
        return (pre[i] + suf[n - j + 1]) / (i + j);
    };

    int l = 1, r = n - 1, ans = 0;
    while(l <= r){
        int mid = (l + r) / 2;
        bool ok = false;
        int low = 1, high = n - mid;
        while(high - low >= 17){
            int mid1 = (2 * l + r) / 3, mid2 = (2 * r + l) / 3;
            int val1 = get(mid, mid1), val2 = get(mid, mid2);
            if(min(val1, val2) < a[mid]){
                ok = true;
                break;
            }
            if(val1 > val2) low = mid1;
            else high = mid2;
        }
        for(int i = low; i <= high; i++){
            if(get(mid, i) < a[mid]){
                ok = true;
                break;
            }
        }
        if(ok){
            ans = mid;
            l = mid + 1;
        }
        else r = mid - 1;
    }
    cout << ans << "\n";
}
signed main() {
    ios_base::sync_with_stdio(false);
    cin.tie(0); cout.tie(0);
    
    int t; cin >> t;
    while(t--) solve();
}

提出情報

ジャッジ結果