HDU 3650 Hot Expo(线段覆盖==离散化)

HDU 3650 Hot Expo(线段覆盖==离散化)

http://acm.hdu.edu.cn/showproblem.php?pid=3650

题意:

一个人要去参加n项活动,这些活动给出了开始时间和结束时间.他只能在每天的指定时间段去参加每项活动.问你他最少要花多少天才能参加完这些活动?

分析:

把一天的时间24*3600秒看成是一个0到24*3600的数轴.那么每个活动其实就覆盖了数轴上的一段线段.然后我们看数轴上的哪段子线段被覆盖最多次,那个最多次数就是我们需要的天数.

本题类似ZOJ1610(但是却有差别):

http://blog.csdn.net/u013480600/article/details/39502473

解法类似上题ZOJ1610,但是下面举个例子:

如果两个活动[1,2] [2,3]需要进行,那么最少需要几天?答案是2天.因为在第2秒的时刻同时有两个活动需要进行,所以是需要2天的. 但是如果同样拿到ZOJ1610去计算那么线段的最大覆盖数就是1(不是2). 因为ZOJ1610明说的是线段,线段上任何一点是可以无穷小的. 而本题的时间单位是秒,也就是说2秒这点不是无穷小,它也是一个区间的. 所以这就是本题和ZOJ1610的区别.

问题是如何解决这个小差别呢? 就是在表示原始线段覆盖的时候,然后它把末尾的那小段也覆盖了就行.(具体看代码标记处)

也就是说:假设原始线段被x坐标离散化分为了0 1 4 5 四个点.现在有一个原始活动为[0,1],那么它的覆盖区间是[0,1]和[1,4].(不仅仅是[0,1]了) 然后再来一个活动[1,4],它的覆盖区间是[1,4]和[4,5].这样我们就至少需要2天才行.

AC代码:

#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
const int maxn=100*2+5;

struct Node
{
    int x1,x2;
}nodes[maxn];

int n;
int x[maxn];
int num;

int main()
{
    while(scanf("%d",&n)==1 && n)
    {
        num=0;
        for(int i=0;i<n;++i)
        {
            scanf("%d%d",&nodes[i].x1,&nodes[i].x2);
            x[num++]=nodes[i].x1;
            x[num++]=nodes[i].x2;
        }
        sort(x,x+num);
        num=unique(x,x+num)-x;

        int cover[maxn];//线段覆盖数
        memset(cover,0,sizeof(cover));
        for(int i=0;i<n;++i)
        {
            int L_x=lower_bound(x,x+num,nodes[i].x1)-x;
            int R_x=lower_bound(x,x+num,nodes[i].x2)-x;

            for(int j=L_x;j<=R_x;++j) ++cover[j];
        }
        int ans=0;
        for(int i=0;i<=num;++i) ans=max(ans,cover[i]);
        printf("%d\n",ans);
    }
    return 0;
}