| ||||||||||
| Online Judge | Problem Set | Authors | Online Contests | User | ||||||
|---|---|---|---|---|---|---|---|---|---|---|
| Web Board Home Page F.A.Qs Statistical Charts | Current Contest Past Contests Scheduled Contests Award Contest | |||||||||
Re:wa了N次 大家给侧测试也能通过 谁能帮看下 修改了下 还waIn Reply To:wa了N次 大家给侧测试也能通过 谁能帮看下 Posted by:ccnuzhang at 2008-04-20 17:12:30 #include <iostream>
#include <algorithm>
using namespace std;
typedef struct interval
{
short f;
short l;
}inter;
bool cmp(inter x,inter y)
{
return x.f<y.f || x.f==y.f && x.l<y.l;
}
inter a[20005];
int main()
{
short n,i,m[5000]={0},j,k,r;
short cnt,x,y;
cin>>n;
for(i=0,k=0;i<n;i++)
{
scanf("%d%d",&x,&y);
for(r=0;r<k;r++)//输入的时候一处理一部分包含的问题
{
if(x<=a[r].f && y>=a[r].l ) break;
if(x>=a[r].f && y<=a[r].l )
{
a[r].f=x,a[r].l=y;
break;
}
}
if(r==k) a[k].f=x,a[k++].l=y;
}
n=k;
for(i=n-1;i>=0;i--)//处理包含的问题,把包含的提出,只留被包含的
{
for(k=i-1;k>=0;k--)
{
if(a[i].f<=a[k].f && a[i].l>=a[k].l)
{
n--;
break;
}
if(a[i].f>=a[k].f && a[i].l<=a[k].l)
{
a[k]=a[i];
n--;
break;
}
}
}
sort(a,a+n,cmp);//排序
m[0]=a[0].l-1;
m[1]=a[0].l;
for(i=1,k=2;i<n;i++)//求最小元素
{
cnt=0;
for(r=k-1;r>=0;r--)
{
if(m[r]>=a[i].f && m[r]<=a[i].l) cnt++;
if(cnt==2 || m[r]<a[i].f) break;
}
r=cnt;
if(cnt==2) continue;
else
{
for(j=a[i].l;j>=a[i].f;j--)
{
if(j==m[k]) continue;
m[k+(1-cnt)]=j;
cnt++;
if(cnt==2) break;
}
k+=2-r;
}
}
cout<<k<<endl;
return 12;
}
Followed by: Post your reply here: |
All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator