題目說(shuō)的有點(diǎn)詭異，一開始沒(méi)想到二分，想直接通過(guò)半平面交來(lái)解或者是線性規(guī)劃。。。
描述下題目平面上有一些點(diǎn)（x,t）（題目中描述的是(t,x)，然后t是縱坐標(biāo)，有點(diǎn)不舒服），然后滿足t2 >= t1+|x2-x1|的點(diǎn)（t1,x1）稱為點(diǎn)(x2,t2)的前導(dǎo)點(diǎn)?，F(xiàn)在知道平面點(diǎn)集以及其前導(dǎo)點(diǎn)的個(gè)數(shù)，問(wèn)其前導(dǎo)點(diǎn)集中t的最大值。
根據(jù)不等式，可以發(fā)現(xiàn)每個(gè)點(diǎn)的前導(dǎo)點(diǎn)集范圍是一個(gè)以該點(diǎn)為頂點(diǎn)的三角形區(qū)域（根據(jù)不等式約束畫個(gè)圖看看就明白了），然后可以通過(guò)二分求得t，關(guān)于判斷當(dāng)前t的可行性，將每個(gè)點(diǎn)表示為合法區(qū)間[x2-(t2-t1),x2+t2-t1]，然后求這些區(qū)間的最小覆蓋數(shù)（就是求得一些子區(qū)間，使得這些子區(qū)間包含于原區(qū)間）。這個(gè)問(wèn)題可以通過(guò)貪心算法，以區(qū)間右端點(diǎn)為第一關(guān)鍵字，左端點(diǎn)為第二關(guān)鍵字進(jìn)行排序，然后每次貪心的選擇當(dāng)前區(qū)間的右端點(diǎn)作為子區(qū)間，統(tǒng)計(jì)要導(dǎo)出全部區(qū)間需要子區(qū)間的個(gè)數(shù)num。
代碼如下：
1 import java.io.*;
2 import java.util.Arrays;
3 public class Main {
4
5 /**
6 * @param args
7 */
8 static StreamTokenizer in=new StreamTokenizer(new BufferedReader(new InputStreamReader(System.in)));
9 //static StreamTokenizer in=new StreamTokenizer(new BufferedReader(new InputStreamReader(new FileInputStream("input.txt"))));
10 static final int readInt() throws Exception
11 {
12 in.nextToken();
13 return (int)in.nval;
14 }
15 static class node implements Comparable<node>
16 {
17 int t,x,s,e;
18 public int compareTo(node pos)
19 {
20 if(e!=pos.e) return e-pos.e;
21 else return s-pos.s;
22 }
23 }
24 static node data[]=new node[100005];
25 public static void main(String[] args) throws Exception{
26 int n=readInt();
27 for(int i=0;i<100005;i++)
28 data[i]=new node();
29 for(int test=1;test<=n;test++)
30 {
31 int num=readInt(),limit=readInt(),e=4000000,s=-4000000;
32 for(int i=0;i<num;i++)
33 {
34 data[i].t=readInt();
35 data[i].x=readInt();
36 e=Math.min(e, data[i].t);
37 }
38 while(s<=e)
39 {
40 int mid=(s+e)>>1,count=1;
41 for(int i=0;i<num;i++)
42 {
43 data[i].s=data[i].x-data[i].t+mid;
44 data[i].e=data[i].x+data[i].t-mid;
45 }
46
47 Arrays.sort(data,0,num);
48 int laste=data[0].e;
49 for(int i=1;i<num;i++)
50 if(data[i].s<=laste)
51 continue;
52 else
53 {
54 count++;
55 laste=data[i].e;
56 }
57 if(count<=limit)
58 s=mid+1;
59 else
60 e=mid-1;
61 }
62 System.out.println("Case "+test+": "+e);
63 }
64
65 }
66
67 }
68