| ||||||||||
| 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 | |||||||||
Re:提供思路! 和比较容易错的情况!自己写了个快排+贪心的!附代码!!!!(仅供参考)In Reply To:提供思路! 和比较容易错的情况!自己写了个快排+贪心的!附代码!!!!(仅供参考) Posted by:2007210562 at 2009-08-11 21:06:44 #include <stdio.h>
#include <algorithm>
using namespace std;
struct cow_t{
int s;
int e;
}cow[255010];
int cmp(struct cow_t a, struct cow_t b)
{
if(a.s == b.s) return a.e < b.e;
return a.s < b.s;
}
int main()
{
int n;
int t;
int i, j;
int start, end;
int cnt = 0;
scanf("%d%d", &n, &t);
for(i = 0; i < n; i++)
{
scanf("%d%d", &cow[i].s, &cow[i].e);
}
sort(cow, cow+n, cmp);
if(cow[0].s == 1)
{
j = 0;
cnt = 1;
start = end = cow[0].e;
while(1)
{
for(i = j + 1; i < n; i++)
{
if(cow[i].s - 1 <= start && cow[i].e > end)
{
end = cow[i].e;
j = i;
}
}
if(end == start) break;
cnt++;
if(cow[j].e == t) break;
start = end = cow[j].e;
}
if(cow[j].e == t) printf("%d\n", cnt);
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