[ACM] POJ 1727 解题报告, 二分+贪心

思路和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 
5struct Event {
6    int t,x,l,r;
7    void calc() {
8        l=x-t;
9        r=x+t;
10    }
11};
12 
13int 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 
19int 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 
40int 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}

Leave a Reply

Your email address will not be published. Required fields are marked *