题目链接

GCJ 2009 R2 A. Crazy Rows

思路

$$ \begin{aligned}从第一行开始贪心选取离它最近的可选行交换。\end{aligned} $$

时间复杂度

$$ O(N^2) $$

代码

#include <cstdio>
#include <iostream>

using namespace std;

const int MAXN = 50;

char s[MAXN];
int a[MAXN];

int main() {
    int T;
    scanf("%d", &T);// don't forget &
    for (int kase = 1; kase <= T; kase++) {
        int n;
        scanf("%d", &n);// don't forget &
        for (int i = 1; i <= n; i++) {
            scanf("%s", s + 1);// no &
            a[i] = 0;
            for (int j = 1; j <= n; j++) {
                if (s[j] == '1') {
                    a[i] = j;
                }
            }
        }
        int ans = 0;
        for (int i = 1; i <= n; i++) {
            for (int j = i; j <= n; j++) {
                if (a[j] <= i) {
                    ans += j - i;
                    for (int k = j; k > i; k--) {
                        swap(a[k], a[k - 1]);
                    }
                    break;
                }
            }
        }
        printf("Case #%d: %d\n", kase, ans);
    }
    return 0;
}