挑战GCJ的标题： crazy row

参考ACRUSH 和 挑战程序竞赛代码。 

题目如下：

链接：

https://code.google.com/codejam/contest/204113/dashboard

Case #X: K

翻译过来， 就是给定一个由0和1组成的矩阵。 只允许交换相邻的两行（第i行和第i + 1行）， 把矩阵化为一个下三角矩阵（主对角线上方的元素都是0）， 最少的交换次数是多少？ （注意， 假设我们给定的矩阵总能化为下三角矩阵）。 具体参考原题目。

分析： 每行的0和1的位置并不重要， 只要知道每行的最后一个1的位置就足够了。 如果将这些位置预先计算好， 那么就能降低行交换的复杂度了。  当有多个行满足某行的要求的时候， 选择距离这行最近的行交换代价最小。 可以先换好第1行， 然后第2行， 一次进行下去。

程序如下：

#include <algorithm>
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cstring>


using namespace std;


const int maxn = 40+5;
int n,A[maxn];

int main(){
	freopen("sample.txt","r", stdin);

	freopen("A_large.txt","w", stdout);

	// reopen FILE * freopen ( const char * filename, const char * mode,
    //                        FILE * stream );
    //Reopen stream with different file or mode
    //Reuses stream to either open the file
    //specified by filename or to change its access mode.
	int testcase;
	scanf("%d", &testcase); // 60
	for(int caseId = 1; caseId <= testcase; caseId++) {
	    int res = 0; // the minimum number of steps required
		char str[maxn]; // maxn = 40 + 5
		scanf("%d", &n); // first case: n = 2
		for(int i = 0; i < n; i++) // i-th row
		{
			scanf("%s", str); //
			int p = -1;
			for(int j = 0; j < n; j++) if(str[j] == '1') p = j;
			A[i]=p; // A[i] 存储的是第i行的数据最后一个1的位置
		}

        for(int i = 0; i < n; i++) {
            int pos = -1; //移动到第i行的行
            for(int j = i; j < n; j++) {
                if(A[j] <= i) {
                    pos = j;
                    break;
                }
            }

            // 完成交换
            for(int j = pos; j > i; j--) {
                swap(A[j], A[j - 1]); // use library function
                res++;
            }
        }
		printf("Case #%d: %d\n",caseId, res);
	}
	return 0;
}

编译，　运行，　结束后，　工程中打开文件，　在ＩＤＥ中查看：

Case #X: K