[ZJ][Greedy+二分搜] b173. 飞船测控站（Stations）
內容 ：
“神 州七号”飞船已经圆满发射成功了，你可知道飞船的顺利运行离不开地面对其的测控吗？因而必须保证飞船运行的轨道被测控站的雷达所全部覆盖，才能正常接受和 传输信号。而由于测控站所控制的范围越小，信号接收情况越好，技术难度也越低。所以我们希望在覆盖整个轨道的前提下，使得测控站所需控制的范围越小越好。 由于条件限制，最多只能建立K个测控范围相同的测控站，而且并不是任何位置都可以建立测控站的，所以需要找出一种方案，使得所需测控的范围尽量小。虽然离真正的模型还有一定差距，但喜欢编程的你当然对此问题跃跃欲试了。
为了你的方便，已经帮你把地球抽象展开成一个N*2M的平面矩阵（N为奇数）。其中前M列是东半球，后M列是西半球，最中间的一行为赤道。为了简化问题，飞船的轨道可以看作是在一条穿越东西半球的经线上空（虽然实际并非如此），在此矩阵表示为第I列和第I+M列（1<=I<=M）两端对接形成的一个环。矩阵的每一个格子中可以建立一个监测站，但某些格子除外(比如其他国家的领土或是条件恶劣的地区)。假设测控半径为R，则每个测控站的控制范围可以向上向下各延伸R个格子，即总长度为2R+1的区间。测控范围的重叠并不会相互影响，并且显然有R>=0且2R+1<=N（因为地球是圆的，测控范围最多只能是一个半球）。
由于飞船有M条可选轨道，所以需要你计算出对于每条轨道，最小的测控半径是多少。注意由于控制的需要，对于任意一条轨道，在东半球的赤道上都必须建立一个测控站，并且保证在东半球的赤道上建站不会有限制。
輸入說明
：
输入的第一行为三个正整数N，M，K表示矩阵的大小以及测控站的数量。保证有（2<=N，M<=1000,2<=K<=2N，N为奇数）。接下来N行，每行2M个字符，如果是1则表示可以放置测控站，否则为0表示无法放置。（保证中间一行的前M个字符一定为1）
輸出說明
：
输出包含M行，每行包含一个正整数，第I行表示第I条轨道所需最小的测控半径R为多少(保证必然有解),轨道从左到右依次编号。
範例輸入 ：
5 2 4 0110 0000 1100 0011 1000
範例輸出 ：
1 2
提示
：
对于轨道1:从第一行第一列开始向下可以展开为0010101001(首尾相连)
对于轨道2:从第一行第二列开始向下可以展开为1010001000(首尾相连)
两条轨道均把可选点全部建站即可。
数据规模:
对于30%的数据,有N,M<=15
对于60%的数据,有N,M<=100
对于100%的数据,有N,M<=1000
出處
：
在东半球的赤道上都必须建立一个测控站
這一句話，我最後才發現的，實在可惡，錯了很久找不到錯誤。
#include <stdio.h>
char g[1005][2005];
char buf[10005];
int check(int m, int N, int K) {
static int i, j, k, cnt, R, flag;
N *= 2, R = 2*m+1;
i = N/4;
cnt = 1, flag = 0;
for(j = 0; j < N;) {
if(j+m >= N-m-1) break;
k = i+j;
if(k+R > i+j && k+R > i+N)
k--;
while(k+R > i+j && buf[k+R] == '0')
k--;
if(k+R > i+j) {
cnt++;
if(cnt > K)
return 0;
j = k+R-i;
} else {
return 0;
}
}
return 1;
}
void solve(int N, int K) {
for(int i = 0, j = 2*N; i < 2*N; i++, j++)
buf[j] = buf[i];
buf[4*N] = '\0';
int l = 0, r = N, m;
while(l <= r) {
m = (l+r)/2;
if(check(m, N, K))
r = m-1;
else
l = m+1;
}
printf("%d\n", r+1);
}
int main() {
int N, M, K;
int i, j;
while(scanf("%d %d %d", &N, &M, &K) == 3) {
for(i = 0; i < N; i++)
scanf("%s", g[i]);
for(i = 0; i < M; i++) {
int idx = 0;
for(j = 0; j < N; j++)
buf[idx++] = g[j][i];
for(j = N-1; j >= 0; j--)
buf[idx++] = g[j][i+M];
buf[idx] = '\0';
solve(N, K);
}
}
return 0;
}