Crazy Rows 2009 Round 2 A

2015-05-08

22:45:28

地址：http://code.google.com/codejam/contest/204113/dashboard

题意：给出一个n，然后是n*n的矩阵，题目保证这个矩阵可以转化为下三角矩阵，问最少的操作数，使它成为下三角矩阵。

其实对于矩阵的每一行，我们只需保留它最后一个1所在的列数就好了。

a[i] 为第i行的最右的1所在的列

目的：a[i]要放在的行数应该>=a[i]行&&<=n行

则这样相当于操作一个数组a

从第一行开始找，找到一个可以放在第一行的a[i]，(即a[i]<=1),然后把它放在第一行

从第二行开始找，找到一个可以放在第2行的a[i],(即a[i]<=2),然后把它放在第2行

从第3行开始找......

#include<cstdio>
#include<cstring>
#include<algorithm>

using namespace std;

const int maxn=44;

#define LL long long

int a[maxn];

int main()
{
    freopen("A-small-practice.in","r",stdin);
    freopen("out.txt","w",stdout);

    int test;

    scanf("%d",&test);

    int cas=1;

    while(test--)
    {
        int n;
        scanf("%d",&n);

        for(int i=1;i<=n;i++)
        {
            char str[maxn];
            scanf("%s",&str);

            int len=strlen(str);
            for(int j=len-1;j>=0;j--)
            {
                if(str[j]=='1')
                {
                    a[i]=j+1;
                    break;
                }
                a[i]=0;
            }
        }

        int ans=0;

        for(int i=1;i<=n;i++)
        {
            int pos=0;
            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]);
                ans++;
            }
        }

        printf("Case #%d: %d
",cas++,ans);
    }

    return 0;
}