【贪心】监测点
<center>
提交: 25 解决: 10
[提交][状态][讨论版] </center>
问题 Y: 【贪心】监测点
时间限制: 1 Sec 内存限制: 64 MB提交: 25 解决: 10
[提交][状态][讨论版] </center>
题目描述
“多么希望有一天突然惊醒，发现自己是在小学的一节课上睡着了，现在经历的一切都是一场梦，桌上满是你的口水。你告诉同桌，说做了一个好长好长的梦。同桌骂你白痴，叫你好好听课。你看着窗外的球场，一切都那么熟悉，一切还充满希望……”张琪曼通过时空监测点听到40年前的小墨老师对李旭琳这样说。
话说张琪曼等人将历史时间线划分了n个区域，我们可以将之看成是数轴上的n个闭区间[ai，bi]。现要设置尽量少的监测点，使得每个区间内都至少有一个点（不同区间内含的点可以是同一个），请问需要多少个监测点？
话说张琪曼等人将历史时间线划分了n个区域，我们可以将之看成是数轴上的n个闭区间[ai，bi]。现要设置尽量少的监测点，使得每个区间内都至少有一个点（不同区间内含的点可以是同一个），请问需要多少个监测点？
输入
第一行为一个整数Ｘ，表示有Ｘ组数据，每组数据第一行为一个整数n（N≤100)，表示有n个闭区间，随后n行每行为两个整数，表示区间左端a和右端b(0≤a≤b≤100）。
输出
一个整数，即监测点个数。
样例输入
1
3
1 5
2 8
6 9
样例输出
2
思路：要求输出最少的监测点个数，就需要每个点尽量在更多的区间内，每次取每个区间最后的那个点，可以使此点在后序的尽量多的区间内。
代码：
#include <iostream> #include <cstdio> #include <algorithm> using namespace std; struct node{ int begin; int end; }; node tt[105]; int cmp(node a,node b){ return a.end<b.end||a.end==b.end&&a.begin<b.begin; } int main() { int n; int t; int s=0; int c; int k;//记录上一个计入的节目。 scanf("%d",&c); for(int ii=0;ii<c;ii++){ scanf("%d",&n); for(int i=0;i<n;i++){ scanf("%d %d",&tt[i].begin,&tt[i].end); } sort(tt,tt+n,cmp); s+=1; k=0; for(int i=1;i<n;i++){ if(tt[i].begin>tt[k].end){ s++; k=i; } } printf("%d\n",s); s=0; } return 0; } /************************************************************** Problem: 2229 User: zz13 Language: C++ Result: 正确 Time:0 ms Memory:1700 kb ****************************************************************/
网易公司福利 153人发布
查看3道真题和解析