6656 Watching the Kangaroo
Day by day number of Kangaroos is decreasing
just like
tiger, whale or lions. So I decided to make them a
sanctuary
where they will live peacefully. I do not let visitors go
near
them. So I planted some display screen outside the
sanctuary. For this
problem, you may assume the sanctuary
to be a long line of 1000000000 unit
distance. The leftmost
position is marked with 0 and the rightmost position
with
1000000000. There are at most 100000 cameras on this line.
Each of
the cameras is described with (L; R) which means
that camera covers a range
from position L to position R
inclusive. Each of the cameras has their
associated display
screens outside where the visitors can see the
Kangaroos.
Now for the convenience of the spectators we announce time to
time: \Kangaroo appears in Screen
3", \Kangaroo appears in Screen 7" and so
on. I have some employees who continuously monitor the
position of Kangaroos
and inform the system (here position is a marker). The system chooses the
best
screen to display that animal based on the coverage. The coverage of a
screen for a position x is de ned
as follows:
If the position x is outside
the range of that screen (i.e. x < L or x > R) then the coverage is
zero.
Otherwise the coverage is min(x L; R x).
An example will make it
clear:
Suppose there are four screens covering the range (7, 15), (14, 100),
(8, 10) and (1, 11). Now say
one Kangaroo appears at x = 10.
First screen
has coverage of 3 unit around x = 10. Because x = 10 is within (7, 15) and
min(10
7; 15 10) = min(3; 5) = 3.
Second screen has coverage of 0 unit
around x = 10. Because x = 10 does not belong to the range
(14,
100).
Third screen has coverage of 0 unit around x = 10. Because though x =
10 is within (8, 10) but
min(10 8; 10 10) = 0.
Fourth screen has
coverage of 1 unit around x = 10. Because x = 10 is within (1, 11) and min(10
1; 11 10) = 1.
So which one is better? Obviously the rst one, as it has
the maximum coverage.
So you are given the ranges of the screens and the
positions the kangaroo appears. For each position
of the Kangaroo you are to
tell me the maximum coverage you can have with any of the
screens.
Input
First line of the test le contains T (T 3), number of
test cases. Hence T cases follow. For each case
you are given N, M in the
rst line; N is the number of screens and M is the number of
Kangaroo
appearance (1 N; M 100000). In the next N lines you are given
the range of screens L R
(0 L R 1000000000). Next M lines contain the
position of the Kangaroo | an integer x
(0 x 1000000000).
Output
For each case print the case number. Hence print M lines, i-th
containing the maximum coverage you
can have around i-th
Kangaroo.
Warning: The judge input le is around 6 MB. So use faster I/O
functions.
Sample Input
1
3 2
7 15
14 100
1
11
10
120
Sample Output
Case 1:
3
0
想不到
1 #include <iostream> 2 #include <algorithm> 3 #include <cstdio> 4 #define MAXN 100010 5 #define INF 0x7fffffff 6 using namespace std; 7 typedef struct point 8 { 9 int l,r; 10 } point; 11 point p[110000]; 12 int n,x; 13 int fun(int s) 14 { 15 if (s<0||s>=n) return 0; 16 if (x<p[s].l||p[s].r<x) return 0; 17 return min(x-p[s].l,p[s].r-x); 18 } 19 bool cmp(point x,point y) 20 { 21 if(x.l==y.l)return x.r>y.r; 22 return x.l<y.l; 23 } 24 int main() 25 { 26 int T,i,m,j,nu,l,r,mid; 27 scanf("%d",&T); 28 for(i=1; i<=T; i++) 29 { 30 scanf("%d%d",&n,&m); 31 for(j=0; j<n; j++) 32 scanf("%d%d",&p[j].l,&p[j].r); 33 sort(p,p+n,cmp); 34 nu=1; 35 for(j=1; j<n; j++) 36 { 37 if(p[j].r>p[nu-1].r) 38 p[nu++]=p[j]; 39 } 40 n=nu; 41 printf("Case %d:\n",i); 42 while(m--) 43 { 44 l=0,r=n-1; 45 scanf("%d",&x); 46 while(l<=r) 47 { 48 mid=(l+r)>>1; 49 if(x>p[mid].r||(x<=p[mid].r&&x>=p[mid].l&&x-p[mid].l>=p[mid].r-x)) 50 l=mid+1; 51 else r=mid-1; 52 } 53 printf("%d\n",max(fun(l),fun(r))); 54 } 55 } 56 }
6656 Watching the Kangaroo,布布扣,bubuko.com
原文：http://www.cnblogs.com/ERKE/p/3687915.html
