RustでPOJ 3253を解く

POJ 3253、蟻本にも載ってる。身近な問題がモデルになっているが、ハフマン符号を作るときのアルゴリズムとほとんど一緒で、Queueを使って実装すればで解ける。

この実装では貪欲法でナイーブな実装なので時間計算量は になっているけど、Rustの練習的な側面もあるので今回は妥協する。 競技プログラミング的な文脈ではこれで十分ACが取れる。

use std::mem::swap;

fn main() {
    let mut n = 3;
    let mut l = vec![8, 5, 8];

    let mut ans = 0;
    while n > 1 {
        let mut mii1 = 0;
        let mut mii2 = 1;

        if l[mii1] > l[mii2] {
            swap(&mut mii1, &mut mii2);
        }

        for i in 2..n {
            if l[i] < l[mii1] {
                mii2 = mii1;
                mii1 = i;
            } else if l[i] < l[mii2] {
                mii2 = i;
            }
        }

        let t = l[mii1] + l[mii2];
        ans += t;

        if mii1 == n - 1 { swap(&mut mii1, &mut mii2); }
        l[mii1] = t;
        l[mii2] = l[n - 1];
        n -= 1;
    }

    println!("{}", ans);
}

アルゴリズムについての解説は蟻本p.50に任せる。