Intervals
发布日期:2021-07-14 01:03:49 浏览次数:52 分类:技术文章

本文共 1972 字,大约阅读时间需要 6 分钟。

传送门

描述

You are given n closed, integer intervals [ai, bi] and n integers c1, …, cn.

Write a program that:
reads the number of intervals, their end points and integers c1, …, cn from the standard input,
computes the minimal size of a set Z of integers which has at least ci common elements with interval [ai, bi], for each i=1,2,…,n,
writes the answer to the standard output.

输入

The first line of the input contains an integer n (1 <= n <= 50000) — the number of intervals. The following n lines describe the intervals. The (i+1)-th line of the input contains three integers ai, bi and ci separated by single spaces and such that 0 <= ai <= bi <= 50000 and 1 <= ci <= bi - ai+1.

输出

The output contains exactly one integer equal to the minimal size of set Z sharing at least ci elements with interval [ai, bi], for each i=1,2,…,n.

样例

  • Input
    5
    3 7 3
    8 10 3
    6 8 1
    1 3 1
    10 11 1
  • Output
    6

思路

  • 题意:找一个区间z的大小,满足给定n组abc中,z在[a,b]中至少c个数,求最小的区间大小
  • 求最小值,找最长路
  • 用i表示0~i中在z的数,对于相邻的两个数i和i+1,满足:i+1 - i<=1 , i+1 - i >=0,故建边i+1 i -1,i i+1 0
  • 对于给定的a,b,c:因为是闭区间,所以满足b+1 - a >=c,故建边 a b+1 c
  • spfa 链式向前星

Code

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48
#include
#include
#include
#include
#include
#define LL long long #define INIT(a,b) memset(a,b,sizeof(a)) using namespace std; const int maxn=5e4+7; struct Node{
int To,Dis,Next;}; Node Edge[500005];int top=0; int Begin[maxn],used[maxn],dis[maxn],n=-1,m; void add(int x,int y,int w){
Edge[top]=(Node){y,w,Begin[x]}; Begin[x]=top++; } int spfa(int t){
INIT(used,0);INIT(dis,-1); dis[t]=0; queue
road; road.push(t);used[t]=1; while(!road.empty()){ int now=road.front();used[now]=0;road.pop(); for(int i=Begin[now];i!=-1;i=Edge[i].Next){ int ne=Edge[i].To; if(dis[ne]

转载地址:https://blog.csdn.net/cpongo3/article/details/89334332 如侵犯您的版权,请留言回复原文章的地址,我们会给您删除此文章,给您带来不便请您谅解!

上一篇:乘法逆元的具体求法
下一篇:高斯消元模板

发表评论

最新留言

路过按个爪印,很不错,赞一个!
[***.219.124.196]2024年02月28日 21时51分55秒

关于作者

    喝酒易醉,品茶养心,人生如梦,品茶悟道,何以解忧?唯有杜康!
-- 愿君每日到此一游!

推荐文章

linux以root账号登陆gnome,CentOS 7 - 以root身份登入Gnome 2019-04-21
linux crontab 备份数据库 空文件,Linux下使用crontab自动备份数据库 2019-04-21
linux批处理模式,巧用linux-top的批处理模式 2019-04-21
linux信号量机制例题,第二章 信号量机制及几个经典例题 2019-04-21
linux ba 模拟,在你的 Python 游戏中模拟引力 | Linux 中国 2019-04-21
c语言表达式3649的值是,535个C语言经典实例目录.doc 2019-04-21
c语言Wndproc未定义,小弟我用c语言写了一个windows窗口,为什么有提示未定义的变量类型... 2019-04-21
c语言中malloc数组,如何在C中对malloc()数组进行一行赋值? 2019-04-21
c语言调存储过程,写留言板–调用存储过程出问题 2019-04-21
c语言编程max,C语言编程题及答案.doc 2019-04-21
android测试页面,自动执行界面测试 | Android 开发者 | Android Developers 2019-04-21
android 图片点击变色,Android开发实现ListView点击item改变颜色功能示例 2019-04-21
android增删改查布局,Android之父_增删改查 2019-04-21
vowifi android开关,如何配置VoLTE, ViLTE and VoWifi(IMS config for VoLTE, ViLTE and VoWifi) 2019-04-21
电脑端的mafsvr服务关掉_网吧才是电脑优化的精髓!学会3招你也不用羡慕网吧的流畅了... 2019-04-21
html获取文件路径_HTML 文件路径 2019-04-21
mysql滴的一声就关了_关于mysql数据库在输入密码后,滴的一声直接退出界面的解决办法(详细办法)... 2019-04-21
mysql in 有序_mysql中的in排序 mysql按in中顺序来排序 2019-04-21
mysql 行转列 显示_mysql 行转列 (结果集以坐标显示) 2019-04-21
mysql 完全备份恢复吗_MySQL完全备份与恢复 2019-04-21