一個區間問題。
以下是我的代碼：
#include<stdio.h>
typedef struct
{
long begin,end;
}length;
void qsort(length a[],long ii,long jj)
{/**//*快速排序，按 begin 升序排列*/
long i=ii,j=jj,mid=a[(ii+jj)/2].begin;
length t;
do{
while(a[i].begin<mid) i++;
while(a[j].begin>mid) j--;
if(i<=j)
{
t=a[i];a[i]=a[j];a[j]=t;
i++; j--;
}
}while(i<=j);
if(i<jj) qsort(a,i,jj);
if(j>ii) qsort(a,ii,j);
}
int main()
{
length l[20000];
long k,i,t,ans;
scanf("%ld",&k);
for(i=0;i<k;i++)
{
scanf("%ld%ld",&l[i].begin,&l[i].end);
if(l[i].begin>l[i].end)
{ t=l[i].begin;l[i].begin=l[i].end;l[i].end=t; }
}
qsort(l,0,k-1);
for(i=0;i<k-1;i++)
{/**//*處理重疊區間*/
if( l[i].end>=l[i+1].begin && l[i+1].end>=l[i].end)
l[i].end=l[i+1].begin;
else if( l[i].begin<=l[i+1].begin && l[i].end>=l[i+1].end )
{
t=l[i].end;
l[i].end=l[i+1].begin;
l[i+1].end=t;
}
}
ans=0;
for(i=0;i<k;i++)
ans += l[i].end-l[i].begin;
printf("%ld\n",ans);
return 0;
}
posted on 2010-01-06 19:16
lee1r 閱讀(258)
評論(0) 編輯 收藏 引用 所屬分類:
題目分類：數據結構