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;
}
分享到:
相关推荐
hdu 1166线段树代码
hdu 1166线段树
poj 2528 需要离散化,建树不同,需要处理不同->注意这组数据 3 1 10 1 3 6 10 the ans is 3. hdu 1754 求区间最大值 hdu 1166 求区间和 hdu 1698 成段更新 poj 3468 成段更新 ural 1019 覆盖加统计最长同一个颜色 ...
本人杭电上题目java实现的代码,绝无其他无用的内容,知道的都晓得这是什么
从简单入门到偏中等的几个题,线段树很灵活,主要懂了lazy操作,其他的自己yy吧。
hdu os lesson=============linux kernel 4.13.11
HDU的1250,主要是利用高精度加法,但是代码有点繁琐,效率不是很高
杭电ACMhdu1163
HDU1059的代码
hdu1001解题报告
hdu 1574 passed sorce
HDU的一题........HDU DP动态规
【hdu5306】Gorgeous Sequence 线段树区间最值操作-附件资源
hdu2101AC代码
hdu acm 教案 搜索入门 hdu acm 教案 搜索入门
搜索 dfs 解题代码 hdu1241
Hdu 3333解题报告 题意描述: 给你n个数现在要你求在k个区间上[ai, bi]的不相同的数之和各是多少. N<=30,000; k<=100,000; 显然,这题不能用暴力来做。 这题我们选择用线段数来做。
hdu 5007 Post Robot 字符串枚举。 暴力一下就可以了。
hdu acm 教案 动态规划(1) hdu acm 教案 动态规划(1)
ACM HDU题目分类,我自己总结的大概只有十来个吧