挑战2.7.2 Round 2 2009A. Crazy Rows贪心

题目链接:

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

题意:

题解:

我们只关心每一行最后一个1的位置。 考虑第i行应该放什么，就是a[j]<=i的都行，要交换次数最少，就找到离i最近的一行，然后累计答案。

代码:

#include <bits/stdc++.h> using namespace std; typedef long long ll; #define MS(a) memset(a,0,sizeof(a)) #define MP make_pair #define PB push_back const int INF = 0x3f3f3f3f; const ll INFLL = 0x3f3f3f3f3f3f3f3fLL; inline ll read(){ ll x=0,f=1;char ch=getchar(); while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();} while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();} return x*f; } ////////////////////////////////////////////////////////////////////////// const int maxn = 1e5+10; int a[50]; int main(){ freopen("2.7.2_A-large-practice.in","r",stdin); freopen("2.7.2_A-large-practice.out","w",stdout); int T=read(); for(int cas=1; cas<=T; cas++){ int n = read(); char ch; for(int i=0; i<n; i++){ a[i] = -1; for(int j=0; j<n; j++){ scanf(" %c",&ch); if(ch=='1') a[i]=j; } } int res = 0, pos; for(int i=0; i<n; i++){ for(int j=i; j<n; j++){ if(a[j] <= i){ pos = j; break; } } for(int k=pos; k>i; k--){ swap(a[k],a[k-1]); res++; } } cout << "Case #" << cas << ": " << res << endl; } return 0; }