| ||||||||||
| 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 | |||||||||
2376Cleaning Shifts--Why WA?请大家帮忙看看是哪里错了?
谢谢了!!!
#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: |
All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator