SDOI2005 區間

題目描述

現給定n個閉區間[ai, bi]，1<=i<=n。這些區間的并可以表示為一些不相交的閉區間的并。你的任務就是在這些表示方式中找出包含最少區間的方案。你的輸出應該按照區間的升序排列。這里如果說兩個區間[a, b]和[c, d]是按照升序排列的，那么我們有a<=b<c<=d。

請寫一個程序：

讀入這些區間；

計算滿足給定條件的不相交閉區間；

把這些區間按照升序輸出。

輸入輸出格式

輸入格式：

?

第一行包含一個整數n，3<=n<=50000，為區間的數目。以下n行為對區間的描述，第i行為對第i個區間的描述，為兩個整數1<=ai<bi<=1000000，表示一個區間[ai, bi]。

?

輸出格式：

?

輸出計算出來的不相交的區間。每一行都是對一個區間的描述，包括兩個用空格分開的整數，為區間的上下界。你應該把區間按照升序排序。

?

輸入輸出樣例

輸入樣例#1：?復制

5
5 6
1 4
10 10
6 9
8 10

輸出樣例#1：?復制

1 4
5 10


思路：一開始看到題目，還以為是用線段樹（畢竟省選題），但仔細想了想，用線段樹的話好像很麻煩，要維護不少信息呢，況且數據范圍：1<=ai<bi<=1000000，顯然nlogn的算法
無法承受。那么用什么做法呢？
我們可以發現：n比較小只有5萬，那么我們可以考慮枚舉區間。其實，這題有一個類似于貪心的算法，先按照左端點從小到大排序，然后我們把區間看成是線段，如果兩條線段有交集，那么
我們可以視為把這兩條線段合成為一條，顯然，新線段的右端點即為兩條線段中右端點較靠右的那一個。如果線段沒有交集，那么我們直接輸出上一條線段的答案。
這題這么水實在不像是省選原題啊233。

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cmath>
#include<queue>
using namespace std;
const int maxn=5e4+5;
int read()
{int ret=0,f=1;char c=getchar();while(c<'0'||c>'9'){if(c=='-') f=-1;c=getchar();}while(c>='0'&&c<='9'){ret=ret*10+c-'0';c=getchar();}return ret*f;
}
int n;
struct line{int l,r;
}e[maxn];
bool cmp(line A,line B)
{return A.l<B.l;
}
int main()
{n=read();for(int i=1;i<=n;i++){e[i].l=read(),e[i].r=read();}sort(e+1,e+1+n,cmp);int ll=e[1].l,rr=e[1].r;for(int i=2;i<=n;i++){if(e[i].l<=rr) rr=max(rr,e[i].r);else{printf("%d %d\n",ll,rr);ll=e[i].l,rr=e[i].r;}}printf("%d %d\n",ll,rr);return 0;
}

?

?