Beyond the Void
BYVoid
POI 2001 Intervals 区间

对于区间问题,常常使用标记开头结尾后排序,然后扫描的方法解决问题。这道题也不例外,首先把每个区间分开看作两个点,区间[a,b]记做a s(a为s点),b e(b为e点),所有区间都这样,然后按照在数轴上的位置排序,如果坐标相同,s点放前面。从第一个点开始扫描,最初的Level为0,遇到s点就把 Level值加1,遇到e点就把Level值减1。当处理了某个s点,如果Level变成了1,则这个点就是结果中的一个区间的左界。当处理了某个e点, 如果Level变成了0,则这个点就是右界。

例如样例给出的区间[5,6],[1,4],[10,10],[6,9],[8,10],标记后排序,成为 1.s 4.e 5.s 6.s 6.e 8.s 9.e 10.s 10.e 10.e 扫描到每个点的Level依次是1 0 1 2 1 2 1 2 1 0 于是结果就是[1,4],[5,10]。

扫描的时间复杂度为O(N),而快速排序的时间复杂度为O(NlogN),于是算法的总时间复杂度为O(NlogN)。

/* 
 * Problem: POI2001 prz
 * Author: Guo Jiabao
 * Time: 2009.1.6 21:37
 * State: Solved 
*/
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <cstring>

using namespace std;

const int MAX=50001;

struct Interval
{
	int p;
	bool s;
};

int N;
Interval A[MAX*2];

int cmp (const void *a, const void *b)
{
	if ( ((Interval *)a)->p < ((Interval *)b)->p ) return -1;
	else if ( ((Interval *)a)->p > ((Interval *)b)->p ) return 1;
	else if ( ((Interval *)a)->s ) return -1;
	return 1;
}

void init()
{
	int i;
	freopen("prz.in","r",stdin);
	freopen("prz.out","w",stdout);
	scanf("%d",&N);
	for (i=1;i<=N;i++)
	{
		scanf("%d%d",&A[i*2-1].p,&A[i*2].p);
		A[i*2-1].s=true;
		A[i*2].s=false;
	}
	N*=2;
	qsort(A+1,N,sizeof(A[0]),cmp);
}

void solve()
{
	int i,L,Level=0;
	for (i=1;i<=N;i++)
	{
		if (A[i].s)
		{
			Level++;
			if (Level==1)
				L=A[i].p;
		}
		else
		{
			Level--;
			if (Level==0)
				printf("%d %dn",L,A[i].p);
		}
	}
}

int main()
{
	init();
	solve();
	return 0;
}
<h2><span class="mw-headline">区间 </span></h2>

有一些闭区间[ai,bi](i=1、2、…、n),找出区间数最少的表示方案,并按递增的顺序定稿输出文件。当a≤b<c≤d时,我们说区间[a,b]和[c,d]为递增顺序。

任务:

你的任务是编写一个程序完成下列工作:
  • 从文件中读入这些区间;

  • 算出满足上述条件的区间;

  • 把结果写入文件。

    输入:

    文件的第一行是整数n,3≤n≤50000,代表区间个数,以下第i+1行1≤i≤n,有两个用空格分开的的整数ai和bi表示一个闭区间[ai,bi](1≤ai≤bi≤1000000)。

    输出:

    文件包括,所求的不相交闭区间,每行描述一个闭区间,按照递增顺序。每个区间用两个以空格分开的整数表示,分别是该区间的开头和末端。

    输入样例:

    5
      5 6
      1 4
      10 10
      6 9
      8 10

    输出样例:

    1 4
      5 10

上次修改时间 2017-02-03

相关日志