51nod 1133 不重叠线段
解题思路:
本题使用贪心算法,对线段的末端进行贪心。
step1:对线段末端进行升序排列,末端相同,对始端进行升序排列。
step 2(核心):贪心。例如线段序列为:
start:2 1 3 5 6
end :3 5 6 8 10
从第一段线段开始遍历,若当前线段的末端大于下一段线段的始端,则将下一线段的末端置为当前线段的末端。理由:若下一线段存在相不重合的线段,必定也与当前线段的不重合。
总结:之前也做过很多贪心算法类的题目,不论题目怎么变,都可以把它简化成线段是否重合的问题,唯一不同的区别(也是解题的核心部分)在于是始端进行贪心还是末端进行贪心。解题步骤都是按照以上步骤。
源码附上:
#include <iostream>
#include <algorithm>
using namespace std;
struct line
{
int start,end;
}lines[10001];
bool cmp(line a,line b)
{
if(a.end==b.end)
return a.start<b.start;
return a.end<b.end;
}
int main()
{
int N,num=1;
cin>>N;
int i;
for(i=0;i<N;i++)
{
cin>>lines[i].start>>lines[i].end;
}
sort(lines,lines+N,cmp);
for(i=0;i<N-1;i++)
{
if(lines[i].end>lines[i+1].start)
{
lines[i+1].end=lines[i].end;
}
else
{
num++;
}
}
cout<<num<<endl;
return 0;
}