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