PROG-1119: รัฐบาลผสม (coalition)

#include <bits/stdc++.h>
using namespace std;
const int INF = 1e9;
using pii = pair<int,int>;
pii qs[300001];
int main(){

    int n, sum = 0;
    scanf("%d",&n);
    int ar[n+1];

    for(int i=1;i<=n;i++){
        scanf("%d",&ar[i]);
        sum += ar[i];
        qs[i] = {ar[i],i};
    }

    sort(qs+1,qs+n+1,greater<pii>());

    for(int i=2;i<=n;i++) {
        qs[i].first = qs[i-1].first+qs[i].first;
    }

    for(int i=1;i<=n;i++){

        int mn = INF, l =1, r=n, mid;

        while(l <= r){

            mid = (l+r)/2;
            int x = qs[mid].first;
            bool add = true;

            if(ar[i] <= ar[qs[mid].second]) x += ar[i];
            else add = false;
            if(x > sum/2) {
                if(!add) mn = min(mn,mid-1);
                else mn = min(mn,mid);
                r = mid-1;
            }
            else l = mid+1;

        }
        printf("%d\n",mn);
    }


    return 0;
}