2009 round2 : Crazy Rows

keyword

swap回数　行列　greedy　C++

概要

行列が与えられる。隣接する行を入れ替えることにより行列を下三角化したい。必要なswapの最小回数を求める問題。ただし下三角化できることは仮定してよい。
swapの回数は貪欲にやれば最小回数になるはず。それが分かれば後は書くだけ。必要な情報は各行に対して非ゼロの要素が最後に出てくるのは何番目か、ということだけ。必須ではないが無駄な情報は落とした方がわかりやすいと思う。

int main(){
    int i, j, k, t, ans, n;
    char x;
    int ns[50];

    scanf("%d\n",&t);

    LOOP(t){
        ans = 0;
        scanf("%d\n",&n);

        REP(i,n){
            k = -1;
            REP(j,n){
                scanf("%c",&x);
                if(x=='1') k = j;
            }
            scanf(" ");
            ns[i] = k;
        }

        REP(i,n){
            if(ns[i] > i){
                for(j=i+1;ns[j]>i;j++);
                for(;j>i;j--){
                    swap(ns[j],ns[j-1]);
                    ans++;
                }
            }
        }

        printf("Case #%d: %d\n", loopCount, ans);
    }

    return 0;
}