cormoran's note


cormoran

競技プログラミング・電子工作・ロボットなどで遊びます



Recent Post




yukicoder-No322-Geometry-Dash

No.322 Geometry Dash

ソートの比較関数をうまく定義する

解法

難所i,jを

… i … j … のように並べると、時間は

$ (D_i * T_i / 2 + T_i) + (D_j * T_j / 2 + T_j) + ( D_j * T_i ) $ かかる

… j … i … のように並べると、時間は

$ (D_i * T_i / 2 + T_i) + (D_j * T_j / 2 + T_j) + ( D_i * T_j ) $ かかる

差は一番後ろの$D_j*T_i, D_i*T_j$の部分だけなので、

$$ D_j * T_i > D_i * T_j $$ なら .. i .. j の順、そうでなければ .. j .. iにすれば時間がより多くかかる。

よって、この部分を比較関数としてソートすればいい。


struct Data{
    int idx;
    int t, d;
    bool operator < (const Data &r) const {
        return d * r.t < r.d * t;
    }
};

bool solve(){
    int N; cin >> N;
    vector<Data> data(N);
    rep(i, N) data[i].idx = i+1;
    rep(i, N) cin >> data[i].t;
    rep(i, N) cin >> data[i].d;
    sort(all(data));
    rep(i, N){
        cout << data[i].idx << (i!=N-1 ? " " : "\n");
    }
    
    return false;
}

comments powered by Disqus