这其实是一个简单的区间合并问题,但是我们第一交是过了,后来学长rejudge,我们又TLE了,这一下不仅耽误了我们的时间,也波动到了我们的心情,原先时间是2s,(原oj就是2s),后来改成了1s,我用的O(N*N)的循环直接超时了,这并不可怕,可怕的是我们被这个思路误导了,一直在O(N*N)的基础上优化,交了好多次.......最后才知道没有那么复杂,题目中的样例比较特殊,排序后直接O(N)的枚举就可以了,因为水题罚时多,排名特别靠后,我的心好痛T T....
#include<iostream>
#include<cstdio>
#include<algorithm>
using namespace std;
struct EDGE
{
int st,en;
}e[];
bool cmp(EDGE a,EDGE b)
{
return a.st < b.st;
}
int main()
{
int t;
scanf("%d",&t);
for(int i = ;i < t;i++)
{
scanf("%d%d",&e[i].st,&e[i].en);
}
sort(e,e+t,cmp);
int ans = ;
EDGE now = e[];
for(int i = ;i < t;i++)
{
if(e[i].en < now.en)
{
ans++;
}
else now = e[i];
}
printf("%d\n",ans);
return ;
}