C. Space Formula

1400
  • Quiz
  • AC
  • 感想
    • 通したんだけどモヤモヤ・・・
    • "It's guaranteed that given astronaut will have unique number of points before the race."って書かれているから配列Sはunique(同じ数が存在しない)なのでは？
    • (TLEしたのでテストケースを見たらSに同じ数が存在した)
  • 解法
    • D番目の自分が1位を取ったことにして、その時のスコアが基準となる。そのスコアをmeとする
    • レースで1番低い点数を与えてもmeを越えてしまう人には、低い点数を割り振らなくてよく、逆に残っているうちの1番高い点数を割り当てればいい
int main(){
    cin.tie(0);
    ios::sync_with_stdio(false);

    // input
    ll N,D;
    cin>>N>>D;

    // current point
    VI A(N);
    rep(i, N) cin >> A[i];

    // next point
    VI P(N);
    rep(i, N) cin >> P[i];

    ll me = A[D-1] + P[0];
    
    multiset<ll> se;
    rep(i,N){
      if(i==D-1)continue;
      se.insert(A[i]);
    }

    ll rank=1;
    FOR(i,1,N){
      ll p = P[i];
      // この大きいポイントを誰に与えるか
      auto it = se.begin();
      if(*it + p <= me){
        se.erase(it);
      }
      else{
        // 1番小さい人に与えても抜けないので、このポイントはseの1番大きい人に与える
        it = se.end();
        it--;
        se.erase(it);
        rank++;
      }
    }
    p(rank);

    return 0;
}