当前位置:编程学习 > C/C++ >>

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++ ,
CopyRight © 2022 站长资源库 编程知识问答 zzzyk.com All Rights Reserved
部分文章来自网络,