Algoogle

Algorithm for Programming Contest

JOI 春合宿 2008 Cheating

Category: JOI Tag: binary-search

Cheating

問題概要


m人の要注意人物がいる.
監視カメラがn個あってこれらの配置を考えたい.
要注意人物が横と縦のどちらでも監視されるようにしたいとき, 監視カメラがカバーしなければいけない幅の最大値の最小を求めよ

解法


幅を2分探索すればよい.
判定はまだ監視されてないならその点を端として監視カメラを設置していってn個で縦横をカバーできるか見る.

コード


(Cheating.cpp) download
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
#include <bits/stdc++.h>
using namespace std;

int n, m;
int x[100010], y[100010];

bool chk(int s[], int k, int &res)
{
        int pv = -1e9-1;
        for (int i = 0; i < m; i++) {
                if(s[i]-pv > k) {
                        res--;
                        pv = s[i];
                }
                if(res<0) return 0;
        }
        return 1;
}

bool ok(int k)
{
        int res = n;
        return chk(x,k,res) and chk(y,k,res);
}

int solve()
{
        sort(x,x+m);
        sort(y,y+m);
        int lb = -1, ub = max(x[m-1]-x[0],y[m-1]-y[0]), mid;
        while(ub-lb>1){
                mid = (lb+ub)/2;
                if(ok(mid)) ub = mid;
                else lb = mid;
        }
        return ub;
}

void input()
{
        cin >> n >> m;
        for (int i = 0; i < m; i++)
                cin >> x[i] >> y[i];
}

int main()
{
        cin.tie(0);
        cin.sync_with_stdio(0);
        input();
        cout << solve() << endl;
        return 0;
}

Comments