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 |
分享两段 贪心代码 分别是以 头较小和尾较大排序//开始看错了 本来A了,看成WA,就写了第二段 #include<stdio.h> #include<string.h> #include<algorithm> using namespace std; struct PP { int a,b; }q[10005]; bool cmp(PP a,PP b) { if(a.b==b.b) return a.b<b.b; return a.b<=b.b; } int main() { int i,j,n,s,sum,flag,e; while(scanf("%d",&n)!=EOF&&n) { for(i=0;i<n;i++) scanf("%d%d",&q[i].a,&q[i].b); sort(q,q+n,cmp); e=q[0].b; s=q[0].b-1; sum=2; for(i=1;i<n;i++) { flag=0; if(e<q[i].a) { sum+=2; s=q[i].b-1; e=q[i].b; } else if(e==q[i].a) { sum++; s=q[i].a; e=q[i].b; } else { if(s>=q[i].a) continue; else { sum++; s=e; e=q[i].b; } } } printf("%d\n",sum); } return 0; } //第二段: 其实思想很第一段差不多 #include<stdio.h> #include<string.h> #include<algorithm> using namespace std; struct PP { int a,b; }q[10005]; bool cmp(PP a,PP b) { if(a.a<b.a) return 1; if(a.a==b.a&&a.b<b.b) return 1; return 0; } int main() { int i,j,n,s,sum,e; while(scanf("%d",&n)!=EOF&&n) { for(i=0;i<n;i++) scanf("%d%d",&q[i].a,&q[i].b); sort(q,q+n,cmp); e=q[0].b; s=q[0].b-1; sum=2; for(i=1;i<n;i++) { if(e<q[i].a) { sum+=2; s=q[i].b-1; e=q[i].b; continue; } if(s<q[i].a) { s=e>q[i].b-1? q[i].b-1:e; e=q[i].b; sum++; continue; } if(e>q[i].b) e=q[i].b; } printf("%d\n",sum); } return 0; } Followed by: Post your reply here: |
All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator