CodeForces 230C Shifts

题目：大意是说给定n行序列，每行序列只由0和1组成，每行序列可以向左循环移动，也可以向右循环移动，问最小的移动次数使得有某一列全部元素为1.

题解：有人是用dp的方法做的，我不会，这里只介绍模拟的方法：就是将每一行的所有的1的位置记录下来，然后将每两个1之间的所有元素看看它们靠两侧哪个1近，然后记录最小移动次数即可，最后将每一列相加，求最小的即可。

#include <iostream>
#include <cstdio>
#include <cstring>
#include <cmath>
#include <vector>
using namespace std;
char s[110][10010];
int t[110][10010];
int main()
{
    int i=0,j,n,m;
    int l[10020],r[10020],flag=1;
    memset(r,0,sizeof(r));
    cin>>n>>m;
    for(i=1;i<=n;i++)
        scanf("%s",s[i]);
    for(i=1;i<=n;i++)
    {
        memset(l,0,sizeof(l));
        for(j=0;j<m;j++)
            if(s[i][j]==‘1‘) l[++l[0]]=j;
        if(l[0]==0)
        {
            flag=0;
            break;
        }
        l[++l[0]]=l[1]+m;
        for(j=1;j<l[0];j++)
        {
            int k=(l[j]+l[j+1])/2;
            int p=l[j];
            for(;p<=k;p++) r[p%m]+=p-l[j];
            for(;p<=l[j+1];p++) r[p%m]+=l[j+1]-p;
        }
    }
    if(flag==0) cout<<"-1"<<endl;
    else{
         int ans=-1;
        for(i=0;i<m;i++)
        if(ans==-1||ans>r[i]) ans=r[i];
      cout<<ans<<endl;
    }
    return 0;
}

CodeForces 230C Shifts,布布扣,bubuko.com

CodeForces 230C Shifts

原文：http://blog.csdn.net/knight_kaka/article/details/22892813