| ||||||||||
| 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