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

2376Cleaning Shifts--Why WA?

Posted by WXuan at 2008-04-23 15:54:50
请大家帮忙看看是哪里错了?
谢谢了!!!
#include <iostream>
#include <vector>
#include <deque>
#include <algorithm>
using namespace std;


struct interval
{
	int begin;
	int end;
};


bool Sort_Criterion(interval a,interval b)
{
	if(a.begin<b.begin)
		return true;
	else if(a.begin==b.begin)
	{
		if(a.end<b.end)
			return true;
		else
			return false;
	}
	else
		return false;
}

int main()
{
	int n,t,i;
	scanf("%d %d",&n,&t);

	deque<interval> cow(n);
	for(i=0;i<n;i++)
		scanf("%d %d",&cow[i].begin,&cow[i].end);

	sort(cow.begin(),cow.end(),Sort_Criterion);//排序

	//第一次清除无用数据
	deque<interval>::iterator it = cow.begin();
	while(it!=cow.end())
	{
		int tmp = (*it).begin;
		it++;
		if(it==cow.end())
			break;
		else
		{
			while(it!=cow.end() && (*it).begin==tmp)//注意两个条件的先后顺序
			{
				cow.pop_front();
				it++;
			}
		}
	}

	//第二次清除无用数据
	bool sign = false;
	deque<interval> middle;
	it = cow.end()-1;
	//deque<interval>::iterator it2 = cow.end()-2;//为什么在这里就不对
	while(it!=cow.begin())
	{
		deque<interval>::iterator it2 = it-1;
		while((it!=cow.begin()) && (((*it).begin > (*it2).begin) && ((*it).end <= (*it2).end)))
		{
			it=it2;
			if(it2!=cow.begin())
				it2--;
		}

		middle.push_back(*it);

		if(it==cow.begin())
		{
			sign=true;
			break;
		}
		else
			it--;
	}
	if(sign==false)
		middle.push_back(*it);

	sort(middle.begin(),middle.end(),Sort_Criterion);

	bool isfulfil = true;
	cow.clear();
	it=middle.begin();
	cow.push_back(*it);
	while(it!=middle.end())
	{
		deque<interval>::iterator it2 = it+1;
		while(it2!=middle.end() && (*it2).begin <= (*it).end)
			it2++;
		if(it2==middle.end())
		{
			if(it2-it>1)
			{
				cow.push_back(*(it2-1));
				break;
			}
			else
				break;
		}
		else
		{
			if(it2-it>1)
			{
				cow.push_back(*(it2-1));
				it=it2-1;
			}
			else
			{
				isfulfil=false;
				break;
			}

		}
	}

	if(isfulfil)
	{
		if(cow[0].begin==1 && cow[cow.size()-1].end>=t)
			printf("%d\n",cow.size());
		else
			printf("-1\n");
	}
	else
		printf("-1\n");

	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