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

好烦啊,一次就AC了,虽然是个小菜逼,还是要装逼一下下

Posted by _Dongdong at 2012-03-14 22:29:48 on Problem 2620
#include <iostream>
#include <algorithm>
#include <stdio.h>
#include <string.h>
#define MAX 100010
using namespace std;

typedef struct 
{
	int a;
	int b;
}Interval;

Interval interval[MAX];
int mark[MAX];

bool cmp(Interval x, Interval y);

bool cmp(Interval x, Interval y)
{
	if(x.a != y.a)
		return x.a<y.a;
	return x.b>y.b;
}

int main(void)
{
	int M, len=0, t=0;
	int a, b;
	int i, j;
	int begin=-1, flag;
	int maxb = -100001;
	scanf("%d", &M);
	while(1)
	{ 
		scanf("%d %d", &a, &b);
		if(a==0 && b==0)
			break;
		interval[len].a = a;
		interval[len].b = b;
		mark[len] = -1;
		len++;
	}
	sort(interval,interval+len,cmp);
	for(i = 0; i < len; i++)
	{
		if(interval[i].a<=0 && interval[i].b>0 && interval[i].b>maxb)
		{
			begin = i;
			maxb = interval[i].b;
		}
		if(interval[i].a > 0)
			break;
	}
	if(begin < 0)
	{
		printf("No solution\n");
		return 0;
	}
	maxb = -100001;
	mark[t++] = begin;
	if(interval[begin].b >= M)
	{
		printf("1\n%d %d\n", interval[begin].a, interval[begin].b);
		return 0;
	}
	for(i = begin; ; i = flag)
	{
		flag = -1;
		for(j = i+1; interval[j].a <= interval[i].b; j++)
		{
			if(interval[j].b >= M)
			{
				mark[t++] = j;
				goto out;
			}
			if(interval[j].b > maxb)
			{
				maxb = interval[j].b;
				flag = j;
			}
		}
		if(flag < 0)
		{
			printf("No solution\n");
			return 0;
		}
		mark[t++] = flag;
	}
out:
	printf("%d\n", t);
	for(i = 0; i < t; i++)
		printf("%d %d\n", interval[mark[i]].a, interval[mark[i]].b);
	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