GCJ 2009 Round 2 Problem A. Crazy Rows

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

题目大意：

给你一个矩阵，让你转化为下三角矩阵，每次只能交换相邻的行，求最小的交换次数。

思路：

一开始觉得记录每一行最后一个1的位置，然后相邻交换排序可以直接冒泡法（甚至可以nlogn的合并排序），结果交上去错的。

想了想因为每一行最后一个1已经满足j<=i了，所以。。（设行i列j）

那么就只好贪心啦，每次选最近的要交换的。

#include<cstdio>

#include<algorithm>

using namespace std;

const int MAXN=50;

char matrix[MAXN][MAXN];

int a[MAXN];

int main()

{

    freopen("e:\\A-large-practice.in","r",stdin);

    freopen("e:\\out.out","w",stdout);

	int T;

	scanf("%d",&T);

	for(int kase=1;kase<=T;kase++)

	{

		int n;

		scanf("%d",&n);

		for(int i=1;i<=n;i++)

			scanf("%s",matrix[i]+1);

		for(int i=1;i<=n;i++)

		{

			a[i]=-1;

			for(int j=1;j<=n;j++)

			{

				if(matrix[i][j]=='1')

					a[i]=j;				//记录每行最后一个1的位置

			}

		}

		int ans=0;

		for(int i=1;i<=n;i++)

		{

			if(a[i] <= i) continue;

			int j;

			for(j=i+1;j<=n;j++)

			{

				if(a[j] <=i)

					break;

			}

			j--;

			for(;j>=i;j--)

			{

				swap(a[j],a[j+1]);

				ans++;

			}

		}

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

	}

    return 0;

}

巴特西

GCJ 2009 Round 2 Problem A. Crazy Rows

最新文章

热门文章