[ZJ][Greedy+二分搜] b173. 飞船测控站（Stations）＠Morris' Blog

2013-02-07 10:28:30| 人氣241| 回應0 | 上一篇 | 下一篇

[ZJ][Greedy+二分搜] b173. 飞船测控站（Stations）

推薦 0 收藏 0 轉貼0 訂閱站台

內容：

“神州七号”飞船已经圆满发射成功了，你可知道飞船的顺利运行离不开地面对其的测控吗？因而必须保证飞船运行的轨道被测控站的雷达所全部覆盖，才能正常接受和传输信号。而由于测控站所控制的范围越小，信号接收情况越好，技术难度也越低。所以我们希望在覆盖整个轨道的前提下，使得测控站所需控制的范围越小越好。由于条件限制，最多只能建立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为多少(保证必然有解),轨道从左到右依次编号。

範例輸入：

範例輸出：

1
2

提示：

样例解释:
对于轨道1:从第一行第一列开始向下可以展开为0010101001(首尾相连)
对于轨道2:从第一行第二列开始向下可以展开为1010001000(首尾相连)
两条轨道均把可选点全部建站即可。

数据规模:
对于30%的数据,有N,M<=15
对于60%的数据,有N,M<=100
对于100%的数据,有N,M<=1000

出處：

2008 海峽兩岸青少年程式設計競賽

在东半球的赤道上都必须建立一个测控站

這一句話，我最後才發現的，實在可惡，錯了很久找不到錯誤。

#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;
}

我要檢舉

#b173#飞船测控站（Stations）

台長： Morris

您可能對以下文章有興趣

d633. 幼稚王國的麥田圖騰

[ZJ][模擬] a632. 12. Domino Rally

[ZJ][bfs, dfs] a634. 14. Knights Path

[ZJ] a473. 外援計畫

人氣(241) | 回應(0)| 推薦 (0)| 收藏 (0)| 轉寄
全站分類: 不分類 | 個人分類: ZeroJudge |
此分類下一篇:[ZJ][字串處理] d313. FROM GENE TO PROTEIN
此分類上一篇:[ZJ] a281. 成為賢惠家庭主婦的第一步從購買划算的食譜開始

回應(0)