贪心数轴 画线问题

xiaoxiao2021-03-01  2

问题描述

三哥无聊的在纸上划着线条,队友不能容忍,于是借机给他出了一个简单的问题,让他把自己画 的n线条选择一部分摆到数轴上,且两两没有重合,然后问他最大的摆放数量k

输入

第一行为一个正整数 n; 在接下来的 n 行中,每行有 2个数 ai,bi描述每条线段。 n, ai, bi(0 < n, ai, bi ≤ 106 )

输出

输出一个整数,为 k的最大值。

输入样例

3

0 2

2 4

1 3

输出样例

2


这是我HPU暑期ACM集训的时候我们学长自己出的题,我们自己的服务器判题,但是当时出了很多BUG

但是总的来说让我们体验了一次区域赛的形式,最后的滚榜还是很刺激的!!!这是个简单的贪心问题 


贪心:

贪心算法是指在对问题求解时,总是做出在当前看来是最好的选择。也就是说,不从整体最优上加以考虑,只做出在某种意义上的局部最优解。贪心算法不是对所有问题都能得到整体最优解,关键是贪心策略的选择,选择的贪心策略必须具备无后效性,即某个状态以前的过程不会影响以后的状态,只与当前状态有关。

#include<iostream> #include<cstdio> #include<algorithm> using namespace std; struct stu //结构体存下在数轴上线段的起点和终点的位置 { int l; int r; }data[1000000+10]; bool cmp(stu x,stu y ) //把这写点的终点按照升序的方法排序; { return x.r<y.r; } int main () { int n; scanf("%d",&n); for(int i=0;i<n;i++) { scanf("%d%d",&data[i].l,&data[i].r); } sort(data,data+n,cmp); //排序 int jishu= 1; int right= data[0].r; //让第一个终点等于我们输入的第0个,也就是第一个 for(int i = 1;i<n;i++) { if(data[i].l>=right) //如果 我们找到了起点的数字大于终点的大小 { //我们的计数器就+1 jishu++; // 然后把交换位置 让后面的一个成 r right=data[i].r; } } printf("%d",jishu); return 0; }

 

转载请注明原文地址: https://www.6miu.com/read-3850144.html

最新回复(0)