首页 > ACM题库 > HDU-杭电 > HDU 3064-twoNumber[解题报告]HOJ
2014
03-01

HDU 3064-twoNumber[解题报告]HOJ

twoNumber

问题描述 :

小白请你帮个忙,在一大堆杂乱无章的数字中,找出两个丢失的数字。
这堆数字虽然杂乱无章,但是有一个特点,就是没有重复的数字,而且排序后可以首尾相连(不过丢失了两个);
由于数字可能会比较多,所以有一部分数字已经被合并压缩:
1 2 3 4 5
可以表示为数字段[1,5];

输入:

输入一个n,表示有多少个数字段输入(0< n<1000000)
接下去输入两个数字,分别代表连续区间中最小的数字和最大的数字 (1<= st <= end <= 1000000),当然这个数字可能已经丢失。
接下去输入n行,每行输入2个数字(St,End)(1<= st <= end <= 1000000)。
St代表数字区间的开始,End代表数字区间的末尾。

输出:

输入一个n,表示有多少个数字段输入(0< n<1000000)
接下去输入两个数字,分别代表连续区间中最小的数字和最大的数字 (1<= st <= end <= 1000000),当然这个数字可能已经丢失。
接下去输入n行,每行输入2个数字(St,End)(1<= st <= end <= 1000000)。
St代表数字区间的开始,End代表数字区间的末尾。

样例输入:

4 
1 15
1 3
7 9
4 6
11 14

样例输出:

10 15
Hint
HINT: be careful with the memory limit;


#include”stdio.h”
#include”string.h”
int hash[1000011];
int main()
{
int i,l;
int a,b;
int n;
int s,e;
int ans1,ans2;
while(scanf(“%d”,&n)!=-1)
   {
scanf(“%d%d”,&s,&e);
for(i=s;i<=e;i++)
hash[i]=0;
for(i=0;i<</FONT>n;i++)
{
scanf(“%d%d”,&a,&b);
for(l=a;l<=b;l++)   
hash[l]=1;
}
for(i=s;i<=e;i++)
if(hash[i]==0) 
{ans1=i;break;}
for(i++;i<=e;i++)      
if(hash[i]==0) 
{ans2=i;break;}
printf(“%d
%d\n”,ans1,ans2);
}
return 0;
}
参考:http://blog.sina.com.cn/s/blog_7dea7e1f0101dyf5.html


  1. 可以参考算法导论中的时间戳。就是结束访问时间,最后结束的顶点肯定是入度为0的顶点,因为DFS要回溯