Submission #65510879

Source Code Expand

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
int main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int T;
    cin >> T;
    while(T--){
        int N;
        cin >> N;
        vector<ll> A(N);
        for(int i = 0; i < N; i++) cin >> A[i];
        sort(A.begin(), A.end());
        vector<ll> ps(N+1, 0);
        for(int i = 0; i < N; i++) ps[i+1] = ps[i] + A[i];
        ll answer = 0;
        for(int i = 0; i < N; i++){
 
 
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX

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

int main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int T;
    cin >> T;
    while(T--){
        int N;
        cin >> N;
        vector<ll> A(N);
        for(int i = 0; i < N; i++) cin >> A[i];
        sort(A.begin(), A.end());

        vector<ll> ps(N+1, 0);
        for(int i = 0; i < N; i++) ps[i+1] = ps[i] + A[i];

        ll answer = 0;
        for(int i = 0; i < N; i++){
            if(i > 0 && A[i] == A[i-1]) continue;
            ll v = A[i];
            ll L = i;
            ll sum_small = ps[i];
            ll deficit_small = L * v - sum_small;
            if(deficit_small <= 0) continue;

            int M = N - i;
            int lo = 1, hi = M, best = 0;
            while(lo <= hi){
                int mid = (lo + hi) >> 1;
                ll sum_big = ps[i + mid] - ps[i];
                ll delta = sum_big - (ll)mid * v;
                if(delta < deficit_small){
                    best = mid;
                    lo = mid + 1;
                } else {
                    hi = mid - 1;
                }
            }
            answer = max(answer, (ll)best);
        }
        cout << answer << "\n";
    }
    return 0;
}

Submission Info

Judge Result