洛谷 2434 [SDOI2005]区间
2024-08-30 22:17:07
【题解】
鲜活的大水题。。。
把区间排个序然后瞎搞就可以了,发现现在区间的左端点比之前区间的最大的右端点还大,那就增加一个答案区间。每次更新目前最大右区间。
#include<cstdio>
#include<algorithm>
#define N 200010
#define rg register
using namespace std;
int n,m,tot;
struct rec{
int l,r;
}a[N],ans[N];
inline int read(){
int k=,f=; char c=getchar();
while(c<''||c>'')c=='-'&&(f=-),c=getchar();
while(''<=c&&c<='')k=k*+c-'',c=getchar();
return k*f;
}
inline bool cmp(rec x,rec y){
if(x.l==y.l) return x.r<y.r;
return x.l<y.l;
}
int main(){
n=read();
for(rg int i=;i<=n;i++) a[i].l=read(),a[i].r=read();
sort(a+,a++n,cmp);
ans[tot=].l=a[].l;
int mxr=ans[].r=a[].r;
for(rg int i=;i<=n;i++){
if(a[i].l>mxr){
ans[++tot].l=a[i].l;
ans[tot].r=a[i].r;
}
mxr=max(mxr,a[i].r);
ans[tot].r=mxr;
}
for(rg int i=;i<=tot;i++) printf("%d %d\n",ans[i].l,ans[i].r);
return ;
}
最新文章
- c语言函数
- 第二章:搭建Android开发环境
- BulkyCopy .Net
- BZOJ4034 T2
- Android网络编程系列 一 TCP/IP协议族
- SIMATIC IT HISTORIAN在烟用二醋酸纤维素生产中应用
- StreamWriter和StremReader简单的用法
- IE css expression(表达式)
- 4.关于phpstudy for linux 的安装(LNMP)更好的环境请看8.LNMP环境
- DateTime用法二
- 设计模式--委托模式C++实现
- 【Android】用Cubism 2制作自己的Live2D——初探Live2D在Android上的运行!
- CodeForces 630G Challenge Pennants (组合数学)
- linux固定IP
- BigDecimal最基础用法【转】
- 超漂亮的CSS3按钮制作教程分享
- ASP.NET Core分布式项目实战-目录
- Boost.Asio 网络编程([译]Boost.Asio基本原理)
- 关于webpy模板自动HTML转义的问题
- vuecli3 引入script 针对没有cmd amd require等方式的js