2014-01-04 13:06:50Morris
[UVA][二分] 12715 - Watching the Kangaroo
SampleInput
題目描述：
給一堆區間，接著詢問座標 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;
}
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;
}