二分的好題。錯了幾次。關鍵是需要考慮周全，不然容易跪。。枚舉以i(0<i<m) 為最終放至全為1的列，那麼只要只知道 i 最靠近i的左右兩邊含有1的列最靠近 i，有可能是末尾或則開頭的那個含1的列。因為可以移動。 [cpp] #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; }
