Crazy Rows(GCJ 2009 Round 2A)

crazy_rows.md

#Crazy Rows(GCJ 2009 Round 2A)

題目

Greedy, 針對第 pos 行, 向後尋找最近的、能放在第 pos 行的 row。

last[i] = the last index of '1' in row i

Code

#include <iostream>
#include <vector>
#include <algorithm>
#include <string>
#include <cstring>

using namespace std;

int main() {
    int T;
    cin >> T;

    for (int case_ = 1; case_ <= T; case_++) {
        int N;
        cin >> N;

        int last[N];
        for (int row = 0; row < N; row++) {
            string inp;
            cin >> inp;

            last[row] = inp.find_last_of('1'); // -1 if not found
        }

        int cnt = 0;
        for (int row = 0; row < N; row++) {
            int temp = row;
            while (last[temp] > row)
                temp++;

            cnt += temp - row;

            while (temp > row) {
                swap(last[temp], last[temp-1]);
                temp--;
            }
        }

        cout << "Case #" << case_ << ": " << cnt << endl;
    }
    return 0;
}