题目链接

题目大意：

给定一些点的坐标代表“事件”，每个“事件”可以有一些“因事件”，只要“因事件”的坐标落在给定不等式确定的范围之内即可。另给定数m表示至多有m个“因事件”。求对于给定的所有事件，它们的“因事件”中，最早发生的那一个事件的最迟发生时间（即最大的纵坐标）。

要做这道题，首先推荐一道非常类似的题目Poj 1328题解，为什么说他们类似呢？对于这么一个最大化最小值的问题，我们显然可以联想到二分，那么最重要的问题就在于，给定一个值$k$，我们要能判断出来他能否是那个最大的最早到达时间。

对于一个给定的$k$值，最优的情况是所有的$m$个cause都是在$k$时间到达的（越早越好），因此这可以成为我们的一个假设。然后我们将存储在$a$数组中的点对按照$x$从小到大的顺序排列，那么是不是就形成了这样一个图？$y=k$是我们所有的cause所在的直线，每个因事件就是$y=k$轴上的一个点，此时求出最少需要多少因事件才能覆盖图上的所有点（转化完毕）。唯一不同的是，这里的每个点比如$P_1(x,y)$，能覆盖它的范围不是一个圆，而是一个等腰直角三角形（右图），$横坐标处于x_1-x_2$范围内的因事件就可以产生$P_1$事件。$x_1=x-(y-k),x_2=x+y-k$，这两个坐标也很好计算，然后就二分答案即可。

//k作为最早的case出现的时间
bool check(int k) {
//每次尽可能让这个点向右靠拢
int x = (a[0].t - k) + a[0].x, cnt = 1;
for (int i = 1; i < n; i++) {
if (x < a[i].x - (a[i].t - k)) {//当前的cause不能产生这个点
x = a[i].t - k + a[i].x;
cnt++;
if (cnt > m)return false;
}
else if (a[i].t - k + a[i].x < x)
x = a[i].t - k + a[i].x;
}
return true;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

#define ll long long
#define inf 0x3f3f3f3f
#define vec vector<int>
#define P pair<int,int>
#define MAX 100005

struct E {
int t, x;
E(int a = 0, int b = 0) { t = a, x = b; }
}a[MAX];
bool cmp(E e1, E e2) {
if (e1.x == e2.x)return e1.t < e2.t;
else return e1.x < e2.x;
}
int T, n, m, l, r;

//k作为最早的case出现的时间
bool check(int k) {
//每次尽可能让这个点向右靠拢
int x = (a[0].t - k) + a[0].x, cnt = 1;
for (int i = 1; i < n; i++) {
//当前的cause不能产生这个点
if (x < a[i].x - (a[i].t - k)) {
x = a[i].t - k + a[i].x;
cnt++;
if (cnt > m)return false;
}
else if (a[i].t - k + a[i].x < x)
x = a[i].t - k + a[i].x;
}
return true;
}
int main() {
scanf("%d", &T);
for (int i = 1; i <= T; i++) {
scanf("%d %d", &n, &m);
r = inf;l = -2000010;
for (int i = 0; i < n; i++) {
scanf("%d %d", &a[i].t, &a[i].x);
if (a[i].t < r)r = a[i].t;
}
r++;
sort(a, a + n, cmp);
while (r - l > 1) {
int mid = (r + l) >> 1;
if (check(mid))l = mid;
else r = mid;
}
printf("Case %d: %d\n", i, l);
}
}
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