Advertisement
YEZAELP

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

Jul 11th, 2020
87
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 0.95 KB | None
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3. const int INF = 1e9;
  4. using pii = pair<int,int>;
  5. pii qs[300001];
  6. int main(){
  7.  
  8.     int n, sum = 0;
  9.     scanf("%d",&n);
  10.     int ar[n+1];
  11.  
  12.     for(int i=1;i<=n;i++){
  13.         scanf("%d",&ar[i]);
  14.         sum += ar[i];
  15.         qs[i] = {ar[i],i};
  16.     }
  17.  
  18.     sort(qs+1,qs+n+1,greater<pii>());
  19.  
  20.     for(int i=2;i<=n;i++) {
  21.         qs[i].first = qs[i-1].first+qs[i].first;
  22.     }
  23.  
  24.     for(int i=1;i<=n;i++){
  25.  
  26.         int mn = INF, l =1, r=n, mid;
  27.  
  28.         while(l <= r){
  29.  
  30.             mid = (l+r)/2;
  31.             int x = qs[mid].first;
  32.             bool add = true;
  33.  
  34.             if(ar[i] <= ar[qs[mid].second]) x += ar[i];
  35.             else add = false;
  36.             if(x > sum/2) {
  37.                 if(!add) mn = min(mn,mid-1);
  38.                 else mn = min(mn,mid);
  39.                 r = mid-1;
  40.             }
  41.             else l = mid+1;
  42.  
  43.         }
  44.         printf("%d\n",mn);
  45.     }
  46.  
  47.  
  48.     return 0;
  49. }
Advertisement
RAW Paste Data Copied
Advertisement