HDOJ 4509 湫湫系列故事——减肥记II(2013腾讯编程马拉松) 并查集合并区间
2024-10-20 16:37:28
发现这种合并区间的题目还可以这么玩
给你n段时间 然后问没被占用的时间是多少
题目所给的区间是右开的导致我wa
好多人5e5*1440的暴力跑出来的时间居然只是我的两倍 不懂....
所以并查集并没有跑的很快 奇怪....
#include <stdio.h>
#include <iostream>
#include <algorithm>
#include <string.h>
#include <math.h>
#include <map>
#include <limits.h>
using namespace std;
typedef long long ll;
const int maxn = 5e5+;
int par[maxn];
int l[maxn],r[maxn];
bool vis[maxn];
void init(int n_)
{
for(int i=;i<=n_;i++)
{
par[i] = i;
l[i] = r[i] = i;
}
memset(vis,false,sizeof(vis));
}
int find(int x)
{
if(x!=par[x])
{
return par[x] = find(par[x]);
}
return x;
}
void unite(int x,int y)
{
x = find(x);
y = find(y);
if(x==y) return ;
par[x] = y;
l[y] = min(l[y],l[x]);
r[y] = max(r[y],r[x]); return ;
}
void make(int x,int y)
{
int pre = x;
for(int i=x;i<y;i==r[find(i)]?i++:i=r[find(i)])
{
//cout<<i<<r[i]<<endl;
if(vis[i])
{
pre = i;
continue;
}
vis[i] = true;
unite(pre,x);
pre = i;
}
}
int main()
{
int n;
int lim = *;
while(scanf("%d",&n)!=EOF)
{
init(lim);
int L = ,R = ,a,b,c,d;
for(int i=;i<n;i++)
{
scanf("%d:%d %d:%d",&a,&b,&c,&d);
L = a*+b;
R = c*+d;
make(L,R); }
int ans = ;
for(int i=;i<lim;i++)
{
if(false==vis[i]) ans++;
}
printf("%d\n",ans);
}
return ;
}
最新文章
- php 实现设计模式之 建造者模式
- HashSet
- Struts2:MyEclippse中使用struts-default.xml中定义的拦截器(timmer,logger)
- 通过System.getProperties()获取系统参数
- NHibernate one-to-one
- UWP深入学习二:各种激活方式
- 使用Thread类可以创建和控制线程
- Nginx与X-Sendfile
- IO(Input&;Output)流の介绍
- 【一天一道LeetCode】#14 Longest Common Prefix
- mysql varcahr转int类型
- SQL中IN与EXISTS的区别
- MapServer Tutorial——MapServer7.2.1教程学习——第一节用例实践:Example1.6 Defining Projections and Extents
- Mybatis面试题
- HDU - 3974 Assign the task (线段树区间修改+构建模型)
- Android 利用二次贝塞尔曲线模仿购物车加入物品抛物线动画
- 那些年的 网络通信之 TCP/IP 传输控制协议 ip 加 端口 ---
- composer安装与应用
- Jenkins关联GitHub进行构建
- const在c和c++中地位不同