思路和yzhw牛一样
1. 每一个event它对应的可能的cause是这个event点下面的三角形区域(这个区域是无穷大的)
2. 问 “the latest time at which the earliest cause could have occurred” 就相当于用一条平行于x轴的直线 t=t0 把这些三角形区域拦腰切断(当然, 此线必须在所有event下面), 只准在腰以上的三角形里放cause. 然后用二分求到一个恰好不能再往上移了的直线, 就成了.
3. 可行性判断, 用贪心. 三角形们和直线相交的那个区间就可以代表这个三角形, 因为放在直线以上的cause都可以垂直投影到直线上, 效果更佳.
4. 在这些所有的区间中, 要找出最少的cause个数n, 使得每个区间内都能包含至少一个的cause. 如果这个n<=m, 那么这条直线ok, 否则不ok.
5. 怎么判断呢, 引用yzhw “以区间右端点为第一关键字,左端点为第二关键字进行排序,然后每次贪心的选择当前区间的右端点作为子区间,统计要导出全部区间需要子区间的个数num。” (其实第二关键字是不用排序的, 无所谓).
6. 对应5, 举个例子
1 | ---------(A) |
2 | ------ |
3 | ------- |
4 | -------- |
5 | ------- |
6 | ------------ |
7 | -----(B) |
8 | ..... ...... |
按照右边界升序排序, 123行显然要放一个点在他们区间里, 放哪呢, “不妨”(这个词表达能力太强了)放在最右边, 即点A处. 然后我们下面所有的左边界<=A的都可以ban掉了, 因为右边界是升序排序的. 这个操作后得到的问题是最优子结构的. 然后到了第7行, A不给力了, "不妨"取一个B. 这些操作整合一下就是维护一个变量rightEdge, 一旦rightEdge不给力就取一个当前区间最右边的点, 同时更新rightEdge至这个点. 之前的错误: 对应6的例子, 我以前是按左边界优先于右边界升序排序的, 那样虽然也对但是无法处理一个区间包含另一个区间的情况, 需要filter一下, filter的过程能写成O(n), 我比较愚钝写的n^2一个case要算2分钟 - -.. 总之这个贪心记住了, 求最小覆盖数 代码点下面:
1 | #include <stdio.h> |
2 | #include <stdlib.h> |
3 | #define DEBUG 0 |
4 |
5 | struct Event { |
6 | int t,x,l,r; |
7 | void calc() { |
8 | l=x-t; |
9 | r=x+t; |
10 | } |
11 | }; |
12 |
13 | int comp( const void *__a, const void *__b) { |
14 | Event *a=(Event *)__a; |
15 | Event *b=(Event *)__b; |
16 | return a->r-b->r; |
17 | } |
18 |
19 | int greed(Event A[], int n, int t0) { |
20 | int *l=( int *) malloc ( sizeof ( int )*(n+1)); |
21 | int *r=( int *) malloc ( sizeof ( int )*(n+1)); |
22 | for ( int i=1;i<=n;i++) { |
23 | l[i]=A[i].l+t0; |
24 | r[i]=A[i].r-t0; |
25 | } |
26 |
27 | int count=0; |
28 | int rightEdge=-2e9; |
29 | for ( int i=1;i<=n;i++) { |
30 | if (l[i]<=rightEdge) |
31 | continue ; |
32 | count++; |
33 | rightEdge=r[i]; |
34 | } |
35 | free (l); |
36 | free (r); |
37 | return count; |
38 | } |
39 |
40 | int main() { |
41 | int N; |
42 | FILE *fp= fopen ( "B.1.dat" , "r" ); |
43 | if (DEBUG) { |
44 | fscanf (fp, "%d" ,&N); |
45 | } |
46 | else |
47 | scanf ( "%d" ,&N); |
48 | for ( int T=1;T<=N;T++) { |
49 | int n,m; |
50 | if (DEBUG) |
51 | fscanf (fp, "%d%d" ,&n,&m); |
52 | else |
53 | scanf ( "%d%d" ,&n,&m); |
54 | Event *A=(Event *) malloc ( sizeof (Event)*(n+1)); |
55 | for ( int i=1;i<=n;i++) { |
56 | int t,x; |
57 | if (DEBUG) |
58 | fscanf (fp, "%d%d" ,&t,&x); |
59 | else |
60 | scanf ( "%d%d" ,&t,&x); |
61 | A[i].t=t; |
62 | A[i].x=x; |
63 | A[i].calc(); |
64 | } |
65 |
66 | qsort (A+1,n, sizeof (Event),comp); |
67 |
68 | int up=1e6; |
69 | int down=-2e6; //because, (-1e6,-1e6) and (-1e6,1e6) intersect at (-2e6,0) |
70 | for ( int i=1;i<=n;i++) |
71 | up=A[i].t<up?A[i].t:up; |
72 | while (1) { |
73 | if (up==down) |
74 | break ; |
75 | if (up==down+1) { |
76 | if (greed(A,n,up)<=m) { |
77 | down=up; |
78 | break ; |
79 | } |
80 | else { |
81 | up=down; |
82 | break ; |
83 | } |
84 | } |
85 | int mid=(up+down)/2; |
86 | if (greed(A,n,mid)>m) { |
87 | up=mid-1; |
88 | continue ; |
89 | } |
90 | else { |
91 | down=mid; |
92 | continue ; |
93 | } |
94 | } |
95 | free (A); |
96 | printf ( "Case %d: %d\n" ,T,up); |
97 | } |
98 | return 0; |
99 | } |