当前位置: 首页 > article >正文

贪心算法-区间问题 C++

题目一

在这里插入图片描述

解题思路

原题解:https://www.acwing.com/solution/content/79913/在这里插入图片描述

代码实现

#include<iostream>
#include<algorithm>

using namespace std;

const int N = 1e5 + 10;

struct Range {
    int l, r;
    
    bool operator < (const Range &w) const {
        return r < w.r;
    }
}range[N];

int main()
{
    int n;
    cin >> n;
    
    for (int i = 0; i < n; i ++ )
    {
        scanf("%d%d", &range[i].l, &range[i].r);
    }
    
    sort(range, range + n);
    
    int res = 0, ed = -0x3f3f3f3f;
    for (int i = 0; i < n; i ++ )
    {
        if (ed < range[i].l)
        {
            res ++;
            ed = range[i].r;
        }
    }
    
    cout << res;
    return 0;
}

题目二

在这里插入图片描述

解题思路

在这里插入图片描述

代码实现

#include<iostream>
#include<algorithm>

using namespace std;

const int N = 1e5 + 10;

struct Range {
    int l, r;
    bool operator < (const Range &w) const {
        return r < w.r;
    }
}range[N];

int main()
{
    int n;
    cin >> n;
    
    for (int i = 0; i < n; i ++ )
    {
        scanf("%d%d", &range[i].l, &range[i].r);
    }
    
    sort(range, range + n);
    int res = 0, ed = -0x3f3f3f3f;
    
    for (int i = 0; i < n; i ++ )
    {
        if (ed < range[i].l)
        {
            ed = range[i].r;
            res ++;
        }
    }
    
    cout << res;
    return 0;
}

题目三

在这里插入图片描述

解题思路

原题解:https://www.acwing.com/solution/content/14773/
在这里插入图片描述

代码实现

#include<iostream>
#include<algorithm>
#include<queue>

using namespace std;

const int N = 1e5 + 10;

struct Range {
    int l, r;
    bool operator < (const Range &w) const
    {
        return l < w.l;
    }
}range[N];

int main()
{
    int n;
    cin >> n;
    
    for (int i = 0; i < n; i ++ )
    {
        scanf("%d%d", &range[i].l, &range[i].r);
    }
    
    sort(range, range + n);
    priority_queue<int ,vector<int>, greater<int>> heap;
    
    for (int i = 0; i < n; i ++)
    {
        if (heap.empty() || range[i].l <= heap.top())
        {
            heap.push(range[i].r);
        }
        else
        {
            heap.pop();
            heap.push(range[i].r);
        }
    }
    
    cout << heap.size();
    return 0;
}

题目四

在这里插入图片描述

解题思路

原题解:https://www.acwing.com/solution/content/16980/
在这里插入图片描述
为什么r = -2e9不能放在for循环内:
例如样例:
4 10 2
4 5
11 12
当第一轮st更新后是5,第二轮j 还是 0,不过此时应该退出了,但如果-2e9放在外面,
if (r < st)
{
res = -1;
break;
}
就不会执行

代码实现

#include<iostream>
#include<algorithm>

using namespace std;

const int N = 1e5 + 10;

struct Range {
    int l, r;
    bool operator < (const Range &w) const {
        return l < w.l;
    }
}range[N];

int main()
{
    int st, ed, n;
    cin >> st >> ed >> n;
    
    for (int i = 0; i < n; i ++ )
    {
        scanf("%d%d", &range[i].l, &range[i].r);
    }
    
    sort(range, range + n);
    
    int res = 0;
    bool flag = false;
    for (int i = 0; i < n; i ++)
    {
        int j = i, r = -0x3f3f3f3f;
        while (range[j].l <= st && j < n)
        {
            r = max(r, range[j].r);
            j ++;
        }
        
        if (r < st)
        {
            flag = true;
            break;
        }
        
        res ++;
        st = r;
        
        if (r >= ed)
        {
            break;
        }
        
        i = j - 1;
    }
    
    if (flag || st < ed)
    {
        res = -1;
    }
    
    cout << res;
    return 0;
}

http://www.kler.cn/a/410781.html

相关文章:

  • 【JavaScript】JavaScript开篇基础(7)
  • .net将List<实体1>的数据转到List<实体2>
  • Spring Boot 应用开发:构建高效、可扩展的 Java 微服务
  • 深入解析分布式遗传算法及其Python实现
  • 【FPGA】Verilog:利用 4 个串行输入- 串行输出的 D 触发器实现 Shift_register
  • 自研芯片逾十年,亚马逊云科技Graviton系列芯片全面成熟
  • 2025职业院校技能大赛信息安全管理与评估(河北省) 任务书
  • 即时通讯服务器被ddos攻击了怎么办?
  • php操作redis
  • 在线客服系统的设计与实现(SpringBoot JPA freemarker MYSQL)
  • L14.【LeetCode笔记】返回倒数第k个节点
  • 《AliCoCo: Alibaba E-commerce Cognitive Concept Net》中文校对版
  • 5分钟上手!用 #Workspace 为 screenshot-to-code 项目增加新功能
  • 华三(H3C)T1020 IPS服务器硬件监控指标解读
  • 游戏引擎学习第23天
  • =computed() =ref()
  • C++ 中的 Lambda 表达式
  • 网络安全基础——网络安全法
  • Kubernetes 分布式存储后端:指南
  • 2024小迪安全基础入门第三课
  • 天洑参展第二届江苏省流体力学学术研讨和产学研会议
  • 第7章 HttpMessageConverter
  • 智尚招聘求职小程序V1.0.18
  • 附录2-pytorch yolov5目标检测
  • 钉钉授权登录
  • C语言使用指针的15大陷阱