cf 230c
二分的好题。错了几次。关键是需要考虑周全,不然容易跪。。枚举以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;
}
补充:软件开发 , C++ ,