Online JudgeProblem SetAuthorsOnline ContestsUser
Web Board
Home Page
F.A.Qs
Statistical Charts
Problems
Submit Problem
Online Status
Prob.ID:
Register
Update your info
Authors ranklist
Current Contest
Past Contests
Scheduled Contests
Award Contest
User ID:
Password:
  Register

分享两段 贪心代码 分别是以 头较小和尾较大排序

Posted by 542935296 at 2011-07-29 15:28:37 on Problem 1716
//开始看错了 本来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:
User ID:
Password:
Title:

Content:

Home Page   Go Back  To top


All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator