24h購物| | PChome| 登入
2014-01-04 13:06:50| 人氣2,220| 回應0 | 上一篇 | 下一篇

[UVA][二分] 12715 - Watching the Kangaroo

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

SampleInput
1
3 2
7 15
14 100
1 11
10
120
SampleOutput
Case 1:
3
0

題目描述：
給一堆區間，接著詢問座標 x 可以在哪個區間內左右展開最大。

題目解法：

二分搜尋左右兩端的最大值，然後二分搜尋是否左邊的最大值大於等於右端點。

#include <stdio.h>
#include <algorithm>
using namespace std;
struct Pt {
    int x, y;
    bool operator<(const Pt &a) const {
        if(x != a.x)
            return x < a.x;
        return y > a.y;
    }
};
Pt D[100005];
int Dx[100005];
int dN;
int prefix[100005];
int main() {
    int testcase, cases = 0;
    int n, m;
    int i, j, k, x;
    scanf("%d", &testcase);
    while(testcase--) {
        scanf("%d %d", &n, &m);
        for(i = 0; i < n; i++) {
            scanf("%d %d", &D[i].x, &D[i].y);
            Dx[i] = D[i].x;
        }
        sort(Dx, Dx+n);
        dN = std::unique(Dx, Dx+n) - Dx;
        for(i = 0; i <= dN; i++)
            prefix[i] = 0;
        for(i = 0; i < n; i++) {
            int dx = std::lower_bound(Dx, Dx+dN, D[i].x) - Dx;
            prefix[dx+1] = max(prefix[dx+1], D[i].y);
        }
        for(i = 1; i <= dN; i++)
            prefix[i] = max(prefix[i], prefix[i-1]);
        printf("Case %d:\n", ++cases);
        while(m--) {
            scanf("%d", &x);
            int l = 0, r = x, mid;
            int L, R, maxval, dx;
            int ret = 0;
            while(l <= r) {
                mid = (l+r)/2;
                L = x - mid;
                R = x + mid;
                dx = std::lower_bound(Dx, Dx+dN, L) - Dx;
                if(dx == dN)    dx--;
                if(Dx[dx] > L)    dx--;
                maxval = prefix[dx+1];
                if(maxval >= R)
                    l = mid+1, ret = mid;
                else
                    r = mid-1;
            }
            printf("%d\n", ret);
        }
    }
    return 0;
}

我要檢舉
#12715#Watching the Kangaroo#二分
台長： Morris

您可能對以下文章有興趣

人氣(2,220) | 回應(0)| 推薦 (0)| 收藏 (0)| 轉寄
全站分類: 教育學習(進修、留學、學術研究、教育概況) | 個人分類: UVA |
此分類下一篇:[UVA] 10461 - Difference
此分類上一篇:[UVA][bfs] 633 - A Chess Knight

我要回應
否 是 (若未登入"個人新聞台帳號"則看不到回覆唷!)
* 請輸入識別碼：
請輸入圖片中算式的結果(可能為0) 
(有*為必填)
TOP
詳全文