【算法】区间(差分约束)

题目

给定 n 个区间 [ai,bi] 和 n 个整数 ci。

你需要构造一个整数集合 Z,使得 ∀i∈[1,n],Z 中满足 ai≤x≤bi 的整数 x 不少于 ci 个。

求这样的整数集合 Z 最少包含多少个数。

输入格式

第一行包含整数 n。

接下来 n 行,每行包含三个整数 ai,bi,ci。

输出格式

输出一个整数表示结果。

数据范围

1 ≤ n ≤ 50000
0 ≤ ai,bi ≤ 50000
0 ≤ ci ≤ bi − ai + 1

输入样例:
5
3 7 3
8 10 3
6 8 1
1 3 1
10 11 1
输出样例:
6

思路

按照样例,我们可以得到一张图。

 差分约束:

(1)求不等式组的可行解

                源点需要满足条件:从原点出发,一定可以走到所有边。

步骤:

【1】先将每个不等式 xi <= xj + ck,转化为一条从xj走到xi的,长度为ck的一条边。

【2】找一个超级源点,使得该源点一定可以遍历到所有的边。

【3】从源点求一遍单源最短路

        结果1:如果存在负环,则原不等式组一定无解。

        结果2:如果没有负环,则dist[ i ]就是原不等式组的一个可行解。

(2)如何求最大值或者最小值,这里的最值指的是每个变量的最值

        结论:如果求的是最小值,则应该是求最长路;如果求的是最大值,则应该是求最短路。

        问题:如何转化x1 <= c,其中一个是常数这类不等式。

        方法:建立一个超级源点,然后建立0 -> i,长度是c的边即可。

代码 

#include<bits/stdc++.h>
using namespace std;
const int N = 200000;
int n;
int h[N],e[N],ne[N],w[N],idx;
int dist[N];
bool st[N];

void add(int a,int b,int c)
{
    ne[idx] = h[a],e[idx] = b,w[idx] = c,h[a] = idx ++;
}

void spfa()
{
    queue<int> q;
    dist[0] = 0;
    q.push(0);
    st[0] = true;
    while(!q.empty())
    {
        int t = q.front();
        q.pop();
        st[t] = false;
        for(int i = h[t]; ~i ; i = ne[i])
        {
            int j = e[i];
            if(dist[j] < dist[t] + w[i])
            {
                dist[j] = dist[t] + w[i];
                if(!st[j])
                {
                    st[j] = true;
                    q.push(j);
                }
            }
        }
    }
}

int main()
{
    memset(dist,-0x3f,sizeof dist);
    memset(h,-1,sizeof h);
    cin >> n;
    for(int i = 1; i <= 50001; i ++)
    {
        add(i-1,i,0);
        add(i,i-1,-1);
    }
    for(int i = 1; i <= n; i ++)
    {
        int a,b,c;
        cin >> a >> b >> c;
        add(a,b + 1,c);
    }
    spfa();
    cout << dist[50001] << endl;
    return 0;
}

题目来自:https://www.acwing.com/

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:/a/151082.html

如若内容造成侵权/违法违规/事实不符,请联系我们进行投诉反馈qq邮箱809451989@qq.com,一经查实,立即删除!

相关文章

解决Github上的README无法显示图片

首先感谢博主的思路&#xff1a;思路 最近写了点东西提交到git 发现本地能查看md里的图片用的相对路径&#xff0c;提交到github就看不见&#xff0c;并且发现不只是我自己的仓库看不见&#xff0c;其他人的我也看不见。那就有问题了 解决&#xff1a;正常使用相对路径&…

【BIM入门实战】Revit图元的选择方式,总有一款适合你

Revit图元的五种常见选择方式,总有一款适合你。 文章目录 一、直接单击二、加选和减选三、连续框选四、按类别选择五、全选过滤选择操作可以在三维视图、平面视图等多种视图中进行。 一、直接单击 直接单击,即可选中某一个图元,如选择一个扶手。 二、加选和减选 按住ctrl键…

32 _ 字符串匹配基础(上):如何借助哈希算法实现高效字符串匹配?

从今天开始,我们来学习字符串匹配算法。字符串匹配这样一个功能,我想对于任何一个开发工程师来说,应该都不会陌生。我们用的最多的就是编程语言提供的字符串查找函数,比如Java中的indexOf(),Python中的find()函数等,它们底层就是依赖接下来要讲的字符串匹配算法。 字符串…

C++二分查找算法:数组中占绝大多数的元素

题目 设计一个数据结构&#xff0c;有效地找到给定子数组的 多数元素 。 子数组的 多数元素 是在子数组中出现 threshold 次数或次数以上的元素。 实现 MajorityChecker 类: MajorityChecker(int[] arr) 会用给定的数组 arr 对 MajorityChecker 初始化。 int query(int left, …

37 _ 贪心算法:如何用贪心算法实现Huffman压缩编码?

基础的数据结构和算法我们基本上学完了,接下来几节,我会讲几种更加基本的算法。它们分别是贪心算法、分治算法、回溯算法、动态规划。更加确切地说,它们应该是算法思想,并不是具体的算法,常用来指导我们设计具体的算法和编码等。 贪心、分治、回溯、动态规划这4个算法思想…

622.设计循环队列(LeetCode)

思路 先确定什么情况为空&#xff0c;什么情况为满。 这里有两种解决方案&#xff0c; 1.留一个空间空置&#xff0c;当rear1 front时 &#xff0c;则队列为满 &#xff08;这里我们选用方案一&#xff09; 2.增加一个size变量记录数据个数&#xff0c;size 0则为空&#xff…

Uniapp导出的iOS应用上架详解

​ 目录 Uniapp导出的iOS应用上架详解 摘要 引言 苹果审核标准 苹果调试 注意事项和建议 总结 摘要 本文将探讨Uniapp导出的iOS应用能否成功上架的问题。我们将从苹果审核标准、性能影响、调试流程等多个方面进行深入分析&#xff0c;以及向开发者提供相关注意事项和建…

【计算机网络笔记】DHCP协议

系列文章目录 什么是计算机网络&#xff1f; 什么是网络协议&#xff1f; 计算机网络的结构 数据交换之电路交换 数据交换之报文交换和分组交换 分组交换 vs 电路交换 计算机网络性能&#xff08;1&#xff09;——速率、带宽、延迟 计算机网络性能&#xff08;2&#xff09;…

JAVA 中集合取交集

日常工作 经常需要取两个数据集的交集。对常用的List 和Set集合做了一个测试 public static void main(String[] args) {List<Integer> list1 Lists.newArrayList();List<Integer> list2 Lists.newArrayList();Set<Integer> set3 Sets.newHashSet();Set&l…

优秀智慧园区案例 - 重庆AI PARK智慧创意园区,先进智慧园区建设方案经验

一、项目背景 1、智慧园区是国家实现经济增长、产业升级的载体 智慧园区建设是城市智慧化创新发展的核心&#xff0c;在数智化升级和低碳化转型的经济发展双引擎的驱动下&#xff0c;十四五、数字经济的政策大力支持&#xff0c;以及人工智能、5G、大数据、区块链等技术的不断…

ubuntu中cuda12.1配置(之前存在11.1版本的cuda)(同时配置两个版本)

ubuntu中cuda12.1配置 由于YOLOv8项目中Pytorch版本需要cuda12.1版本 在官网下载12.1版本的deb包 官网地址 sudo dpkg -i cuda-keyring_1.0-1_all.deb sudo apt-get update sudo apt-get -y install cuda然后需要修改bashrc文件&#xff08;隐藏文件&#xff09; 添加 exp…

Postman实现接口的加密和解密

近期在复习Postman的基础知识&#xff0c;在小破站上跟着百里老师系统复习了一遍&#xff0c;也做了一些笔记&#xff0c;希望可以给大家一点点启发。 1、目前市面上的加密的方式 对称式加密&#xff1a;DES&#xff0c;AES&#xff0c;Base64加密算法 非对称加密&#xff1a…

基于STC12C5A60S2系列1T 8051单片机的数模芯片TLC5615实现数模转换应用

基于STC12C5A60S2系列1T 8051单片的数模芯片TLC5615实现数模转换应用 STC12C5A60S2系列1T 8051单片机管脚图STC12C5A60S2系列1T 8051单片机I/O口各种不同工作模式及配置STC12C5A60S2系列1T 8051单片机I/O口各种不同工作模式介绍数模芯片TLC5615介绍通过按键调节数模芯片TLC5615…

Postman的Cookie鉴权

近期在复习Postman的基础知识&#xff0c;在小破站上跟着百里老师系统复习了一遍&#xff0c;也做了一些笔记&#xff0c;希望可以给大家一点点启发。 一&#xff09;什么是Cookie 定义&#xff1a;存储在客户端的一小段文本信息&#xff0c;格式为键值对的形式. 二&#xff09…

低代码编辑平台后台实现

背景 之前做过一个前端低代码编辑平台&#xff0c;可以实现简单的移动端页面组件拖拽编辑&#xff1a; https://github.com/li-car-fei/react-visual-design 最近基于C的oatpp框架实现了一下后台。使用oatpp框架做web后台开发时&#xff0c;发现按照官方的示例使用的话&#…

氢原子波函数等概率面的绘制

氢原子波函数等概率面的绘制 归一化后的氢原子波函数

高浓度白酒废水处理需要哪些设备

高浓度白酒废水处理需要的设备包括预处理设备、生物反应器、二级处理设备、消毒装置等。 预处理设备&#xff1a;包括格栅、筛网等&#xff0c;用于去除污水中的大颗粒物和杂质。生物反应器&#xff1a;用于进行生物反应&#xff0c;去除污水中的有机物和氨氮等污染物。二级处…

基于平衡优化器算法优化概率神经网络PNN的分类预测 - 附代码

基于平衡优化器算法优化概率神经网络PNN的分类预测 - 附代码 文章目录 基于平衡优化器算法优化概率神经网络PNN的分类预测 - 附代码1.PNN网络概述2.变压器故障诊街系统相关背景2.1 模型建立 3.基于平衡优化器优化的PNN网络5.测试结果6.参考文献7.Matlab代码 摘要&#xff1a;针…

Linux 系统编程,Binder 学习,文件访问相关的接口

文章目录 Linux 系统编程&#xff0c;Binder 学习&#xff0c;文件访问相关的接口1.概念2.linux文件结构3.文件描述符4.Linux文件系统的两类常用接口&#xff0c;linux系统内置库函数4.1 open4.2 close4.3 read4.4 write 5.标准I/O库函数5.1 fopen Linux 系统编程&#xff0c;B…

IDEA 高分辨率卡顿优化

VM设置优化 -Dsun.java2d.uiScale.enabledfalse 增加该条设置&#xff0c;关闭高分切换 https://intellij-support.jetbrains.com/hc/en-us/articles/115001260010-Troubleshooting-IDE-scaling-DPI-issues-on-Windows​intellij-support.jetbrains.com/hc/en-us/articles/1…