C. Platforms Jumping O(N)

1700
  • Quiz
  • AC
  • 解法
    • 最大ジャンプを繰り返した場合、その長さの川まで渡れるかは求められる。それが足りないならNO
    • 足りている場合、platformの間隔を詰めることが問題になる
    • M+1回ジャンプするが、ジャンププランの初期値は最大距離ジャンプにしておき、余分な分を削ってジャンプすればいい
    • 計算量はO(N)
int main(){
    // input
    ll N,M,D;
    cin>>N>>M>>D;

    VI C(N);
    rep(i, N) cin >> C[i];

    ll space = D-1;
    ll longest = space*(M+1) + SUM(C);

    if(longest<N) no();

    ll surplus = longest-N;

    // ジャンプ回数はM+1
    VI J(M+1, D-1); // jump plan
    rep(i,M+1){
      if(surplus){
        ll v = min(J[i], surplus);
        J[i] -= v;
        surplus -= v;
      }
    }

    VI Ans(N, -1);
    ll pos=-1;
    rep(i,M){
      pos += J[i]+1;
      rep(j,C[i]){
        Ans[pos]=i;
        pos++;
      }
      pos--;
    }
    
    p_yes();
    print_vector(Ans);
    
    return 0;
}