当前位置: 代码迷 >> 综合 >> 贪心算法 整数区间
  详细解决方案

贪心算法 整数区间

热度:25   发布时间:2024-01-15 08:47:35.0

【例8】整数区间

题目要求:

请编程完成以下任务:

1. 读取闭区间的个数及它们的描述;

2.找到一个含元素个数最少的集合,使得对于每一个区间,都至少有一个整数属于该集合,输出该集合的元素个数。

【输入】

首行包括区间的数目n,1<=n<=10000,接下来的n行,每行包括两个整数a,b,被一空格隔开,0<=a<=b<=10000,它们是某一个区间的开始值和结束值。

【输出】

第一行集合元素的个数,对于每一个区间都至少有一个整数属于该区间,且集合所包含元素数目最少。

【样例输入】

4

3 6

2 4

0 2

4 7

【样例输出】

2

题意说明:

这题比较难理解,题意为就是你选n个数,保证你输入区间在这n个数至少有一个符合

算法分析:

?算法模型:给n个闭区间[ai,bi], 在数轴上选尽量少的点,使每个区间内至少有一个点。

?算法:首先按b1<=b2<=...<=bn排序。每次标记当前区间的右端点x,并右移当前区间指针(判断x是否大于左端点),直到当前区间不包含x,再重复上述操作。

?如下图,如果选灰色点,移动到黑色点更优。

代码实现:

#include<bits/stdc++.h>
using namespace std;
struct range
{int from,to;              //from开始,to结束
}a[10000];bool cmp(range x,range y)   //按结束排序{return x.to<y.to;}int main(){int n,i,sum=0;cin>>n;for(i=0;i<n;i++)cin>>a[i].from>>a[i].to;sort(a,a+n,cmp);int x;for(i=0,x=-1;i<n;i++)          //初始x的值,保证当下永远小于任意左端点{                              //令x=-1可以使第一个区间与其他区间的操作相同。if(x>=a[i].from)   continue;   //判断上一个右端点是否大于左端点,如果大于则则肯定包含标记号x=a[i].to;                     //更新标记点sum++;        }cout<<sum;return 0;}


  相关解决方案