【问题描述】

现给定n个闭区间[ai,bi]，1<=i<=n。这些区间的并可以表示为一些不相交的闭区间的并。你的任务就是在这些表示方式中找出包含最少区间的方案。你的输出应该按照区间的升序排列。这里如果说两个区间[a, b]和[c, d]是按照升序排列的，那么我们有a<b<=c<=d。

【样例输入】

5 6

1 4

10 10

6 9

8 10

【样例输出】

1 4

5 10

【解题思路】

本题为SDOI 2005 day2 第一题，是区间覆盖问题的变种，其实，看了问题描述后可能不太懂题目的意思，但是看完样例后就会发现，其实就是将一些连在一起的区间合并在一起，最后从小到大输出每个合并后的区间。既然要从小到大，那第一步自然是将每个区间以起点为关键字从小到大排序，然后从第二个区间开始，每个区间与前一个选的区间进行比较，若连在一起，则合并区间，否则，新开一个区间，将这个区间存入新开的区间。注意：除了判断是否连在一起，还要判断终点的大小，如果终点大一些才存，否则无视该区间。

【代码实现】

 type rec=record

      a,b:longint;

 end;

 var c,d:array[..] of rec;

     i,j,n,m,ans,r,w:longint;

 procedure sort(l,r:longint);

 var

  i,j,x:longint;

  y:rec;

 begin

  i:=l;

  j:=r;

  x:=c[(l+r) div ].a;

  repeat

   while c[i].a<x do

    inc(i);

   while x<c[j].a do

    dec(j);

   if not(i>j) then

    begin

     y:=c[i];

     c[i]:=c[j];

     c[j]:=y;

     inc(i);

     j:=j-;

    end;

  until i>j;

  if l<j then

   sort(l,j);

  if i<r then

   sort(i,r);

 end;

 begin

  readln(n);

  for i:= to n do

   with c[i] do

    readln(a,b);

  sort(,n);

  w:=;d[].a:=c[].a;d[].b:=c[].b;

  for i:= to n do

   if (c[i].a<=d[w].b)and(c[i].b>=d[w].b) then//判断区间是否重合，若重合，更新终点

    d[w].b:=c[i].b

   else

    if c[i].a>d[w].b then//若不重合，新开一个区间

     begin

      inc(w);

      d[w].a:=c[i].a;

      d[w].b:=c[i].b;

     end;

  for i:= to w do

   with d[i] do

    writeln(a,' ',b);

 end.

巴特西

区间（vijos 1439) 题解

【问题描述】

【样例输入】

【样例输出】

【解题思路】

【代码实现】

最新文章

热门文章

巴特西

区间 （vijos 1439) 题解

【问题描述】

【样例输入】

【样例输出】

【解题思路】

【代码实现】

最新文章

热门文章

区间（vijos 1439) 题解