小工具知识网

当前位置: 首页 > 行业知识 > 【C++算法】贪心算法-区间问题,超详细注释例题讲解

行业知识

【C++算法】贪心算法-区间问题,超详细注释例题讲解

2026-11-18 02:40:17 来源:互联网转载

文章目录

    • 1)最大不相交区间数(区间选点)
    • 2)区间分组
    • 3)区间覆���

      以下例题来自于AcWing 906~908

      1)最大不相交区间数(区间选点)

      • 翻译一下题目,也就是说给定 N N N个闭区间,问能从中选出多少个区间使其互不相交
      • 贪心策略:新建一个结构体存储区间的左端点和右端点,将这 N N N个区间按照右端点从小到大排序,遍历所有的区间,如果当前遍历到的区间左端点的值大于了上一个区间的右端点的值,说明此时区间没有重合,则区间个数 + 1 +1 +1
        #include#define x first#define y secondusing namespace std;typedef long long ll;typedef pair PII;// 解题思路: const int N=1e5+5; // 区间总数// 区间struct Range {int l; // 左端点int r; // 右端点}range[N];// 按照区间右端点从小到大排序bool cmp(Range a,Range b) {return a.rcin>n;// 输入规模大于1e5,推荐使用速度更快的scanffor(int i=1;iscanf("%d%d",&range[i].l,&range[i].r);}// 计算答案int res=0;int front_r=INT_MIN; // i=1时至少有一个,所以res从0开始sort(range+1,range+1+n,cmp); // 排序for(int i=1;iif(range[i].lfront_r) {res++;front_r=range[i].r; // 更新上一个区间的右端点}}cout 某一分组最大右端点   
        1. 如果存在这样的分组(与某个分组间没有交集),则将区间 $ i $ 放进去,并且更新这个分组的最大右端点(注意,如果与多个分组都有交集则可以放到任意一个分组中,不影响结果,可自行模拟证明)
        2. 如果不存在这样的分组(与每个分组间都有交集),则开一个新组,再把区间 i i i 放进去
        3. 在判断当前区间是否与某一分组有交集时,只需要与所有分组中最小的分组最大右端点进行比较即可,因为这是最有可能满足 r a n g e [ i ] . l   >  某一分组最大右端点 range[i].l \ > \ 某一分组最大右端点 range[i].l > 某一分组最大右端点 的情况,对于所有分组中最小的分组最大右端点,只需要用一个小根堆来维护即可
        #include#define x first#define y secondusing namespace std;typedef long long ll;typedef pair PII;// 解题思路: // 将所有区间按照左端点从小到大排序,从前往后遍历每个区间,判断能否将其放进某个现有的组中// 用堆来维护每个分组的MAX_r,const int N=1e5+5;struct Range {int l;int r;}range[N];bool cmp(Range a,Range b) {// 按照左端点从小到大排序return a.lint n;cin>n;for(int i=1;iint l,r;scanf("%d%d",&l,&r);range[i]={l,r};}sort(range+1,range+1+n,cmp);priority_queue// 如果每个分组中最小的MAX_R都比当前区间的左端点大(说明有交集,不能放入该区间中)if(heap.empty() || heap.top()=range[i].l) {heap.push(range[i].r); // 新开一个分组} else {// 如果无交集,说明可以放入该分组中,此时弹出再更新这个分组的最大值heap.pop(); // 因为rnage[i].r一定比heap.top()更大,不然怎么可能无交集heap.push(range[i].r);}}// 小根堆的大小就是分组的个数cout   int l,r; // 左端点,右端点   // 重载运算符从小到大排序   bool operator   return l   int st,en;   cinsten;   int n;   cinn;   for(int i=1;i   int l,r;   scanf("%d%d",&l,&r);   range[i]={l,r};   }   sort(range+1,range+1+n);   int res=0; // 存储答案   bool success=false;   // 遍历所有区间   for(int i=1;i   // front_r可理解为当前覆盖到的区域   int j=i,front_r=INT_MIN; // 双指针,j从第i个区间开始找   // 取所有左端点能覆盖st中右端点最大的区间,覆盖到这个位置   while(j   front_r=max(front_r,range[j].r);   j++;   }   // 如果front_r仍小于st,说明线段不可被已有区间覆盖   if(front_r   break;   }   // 如果找得到,答案+1   res++;   // 已经完全覆盖   if(front_r=en) {   success=true;   break;   }   // 否则更新i和j   st=front_r; // 迭代st,后面的区间继续和st比   i=j-1; // 双指针,加速遍历   }   if(!success) res=-1;   cout

上一篇:SlN下载指南,轻松上手,简单易懂下载教程

下一篇:服装展示的革命,代码化呈现,轻松实现!