学步园

题目：http://codeforces.com/problemset/problem/230/C

二分的好题。错了几次。关键是需要考虑周全，不然容易跪。。枚举以i(0<i<m) 为最终放至全为1的列，那么只要只知道 i 最靠近i的左右两边含有1的列最靠近  i，有可能是末尾或则开头的那个含1的列。因为可以移动。

#include <cmath>
#include <ctime>
#include <iostream>
#include <string>
#include <vector>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <queue>
#include <map>
#include <set>
#include <algorithm>
#include <cctype>
#include <stack>
#include <deque>
using namespace std;
typedef long long LL;
#define eps 10e-9
#define inf 0x3f3f3f3f
#define REP(i,n) for(int i=0; i<(n); i++)
const int maxn = 100000+100;
vector<int > v[110];
char ma[110][10100];
int main(){
    int n,m;
    scanf("%d %d",&n,&m);
    for(int i=0;i<n;i++){
       scanf("%s",ma[i]);
    }
    for(int i=0;i<n;i++){
       for(int j=0;j<m;j++){
          if(ma[i][j]=='1'){
            v[i].push_back(j);
          }
       }
       if(v[i].size()==0) {
           printf("-1\n");
           return 0;
       }
    }
    int ans=inf;
    for(int i=0;i<m;i++){
        int t_ans=0,right,left;
        for(int j=0;j<n;j++){
            int temp=lower_bound(v[j].begin(),v[j].end(),i)-v[j].begin();
            if(temp<v[j].size())
                 right=v[j][temp]-i;
            else right=maxn;

            right=min(right,v[j][0]+m-i);
            left = m - v[j][ v[j].size()-1 ]+i;
            if(temp<=0)
               t_ans+=min(right,left);
            else{
               t_ans+=min(i-v[j][temp-1],min(right,left));
            }
       //     printf("%d %d %d\n",i,right,left);
        }
        if(t_ans<ans)  ans=t_ans;
    }

    printf("%d\n",ans);

    return 0;
}