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

139 Replies

思路和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, 举个例子
[cpp]
———(A)
——
——-
——–
——-
————
—–(B)
….. ……
[/cpp]
按照右边界升序排序, 123行显然要放一个点在他们区间里, 放哪呢, “不妨”(这个词表达能力太强了)放在最右边, 即点A处. 然后我们下面所有的左边界<=A的都可以ban掉了, 因为右边界是升序排序的. 这个操作后得到的问题是最优子结构的. 然后到了第7行, A不给力了, "不妨"取一个B. 这些操作整合一下就是维护一个变量rightEdge, 一旦rightEdge不给力就取一个当前区间最右边的点, 同时更新rightEdge至这个点. 之前的错误: 对应6的例子, 我以前是按左边界优先于右边界升序排序的, 那样虽然也对但是无法处理一个区间包含另一个区间的情况, 需要filter一下, filter的过程能写成O(n), 我比较愚钝写的n^2一个case要算2分钟 - -.. 总之这个贪心记住了, 求最小覆盖数 代码点下面:
[cpp]

#include <stdio.h>
#include <stdlib.h>
#define DEBUG 0

struct Event {
int t,x,l,r;
void calc() {
l=x-t;
r=x+t;
}
};

int comp(const void *__a,const void *__b) {
Event *a=(Event *)__a;
Event *b=(Event *)__b;
return a->r-b->r;
}

int greed(Event A[],int n,int t0) {
int *l=(int *)malloc(sizeof(int)*(n+1));
int *r=(int *)malloc(sizeof(int)*(n+1));
for(int i=1;i<=n;i++) {
l[i]=A[i].l+t0;
r[i]=A[i].r-t0;
}

int count=0;
int rightEdge=-2e9;
for(int i=1;i<=n;i++) {
if(l[i]<=rightEdge)
continue;
count++;
rightEdge=r[i];
}
free(l);
free(r);
return count;
}

int main() {
int N;
FILE *fp=fopen("B.1.dat","r");
if(DEBUG) {
fscanf(fp,"%d",&N);
}
else
scanf("%d",&N);
for(int T=1;T<=N;T++) {
int n,m;
if(DEBUG)
fscanf(fp,"%d%d",&n,&m);
else
scanf("%d%d",&n,&m);
Event *A=(Event *)malloc(sizeof(Event)*(n+1));
for(int i=1;i<=n;i++) {
int t,x;
if(DEBUG)
fscanf(fp,"%d%d",&t,&x);
else
scanf("%d%d",&t,&x);
A[i].t=t;
A[i].x=x;
A[i].calc();
}

qsort(A+1,n,sizeof(Event),comp);

int up=1e6;
int down=-2e6; //because, (-1e6,-1e6) and (-1e6,1e6) intersect at (-2e6,0)
for(int i=1;i<=n;i++)
up=A[i].t<up?A[i].t:up;
while(1) {
if(up==down)
break;
if(up==down+1) {
if(greed(A,n,up)<=m) {
down=up;
break;
}
else {
up=down;
break;
}
}
int mid=(up+down)/2;
if(greed(A,n,mid)>m) {
up=mid-1;
continue;
}
else {
down=mid;
continue;
}
}
free(A);
printf("Case %d: %d\n",T,up);
}
return 0;
}
[/cpp]

139 thoughts on “[ACM] POJ 1727 解题报告, 二分+贪心”

Leave a Reply

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