Dashboard - Round 2 2009 - Google Code Jam

Problem

You are given an N x N matrix with 0 and 1 values. You can swap any two adjacent rows of the matrix.
Your goal is to have all the 1 values in the matrix below or on the main diagonal. That is, for each X where 1 ≤ X ≤ N, there must be no 1 values in row X that are to the right of column X.
Return the minimum number of row swaps you need to achieve the goal.

http://blog.csdn.net/murmured/article/details/20727051

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

思路：

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

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

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

1. char matrix[MAXN][MAXN];  
2. int a[MAXN];  
3. int main()  
4. {  
5.     freopen("e:\\A-large-practice.in","r",stdin);  
6.     freopen("e:\\out.out","w",stdout);  
7.     int T;  
8.     scanf("%d",&T);  
9.     for(int kase=1;kase<=T;kase++)  
10.     {  
11.         int n;  
12.         scanf("%d",&n);  
13.         for(int i=1;i<=n;i++)  
14.             scanf("%s",matrix[i]+1);  
15.         for(int i=1;i<=n;i++)  
16.         {  
17.             a[i]=-1;  
18.             for(int j=1;j<=n;j++)  
19.             {  
20.                 if(matrix[i][j]=='1')  
21.                     a[i]=j;             //记录每行最后一个1的位置  
22.             }         
23.         }  
24.         int ans=0;  
25.         for(int i=1;i<=n;i++)  
26.         {  
27.             if(a[i] <= i) continue;  
28.             int j;  
29.             for(j=i+1;j<=n;j++)  
30.             {  
31.                 if(a[j] <=i)  
32.                     break;                
33.             }  
34.             j--;  
35.             for(;j>=i;j--)  
36.             {  
37.                 swap(a[j],a[j+1]);  
38.                 ans++;  
39.             }  
40.         }  
41.         printf("Case #%d: %d\n",kase,ans);  
42.     }  
43.     return 0;  
44. } 

Also check code from https://github.com/TomConerly/Competition-Programming/blob/master/GCJ/y2009/Round2/A.java
Read full article from Dashboard - Round 2 2009 - Google Code Jam