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

贪心算法的思路和典型例题

一、贪心算法的思想

贪心算法是一种求解问题时,总是做出在当前看来是最好的选择,不从整体最优上加以考虑的算法。

二.用贪心算法的解题策略

其基本思路是从问题的某一个初始解出发一步一步地进行,根据某个优化测度,每一步都要确保能获得局部最优解。贪心算法的关键在于贪心策略的选择,而不是对所有问题都能得到整体最优解。若下一个数据和部分最优解连在一起不再是可行解时,就不把该数据添加到部分解中,直到把所有数据枚举完,或者不能再添加算法停止。”

三典型题 

第五维度

零维是点,点动成线;

一维是线,线动成面;

二维是面,面动成体;

三维是体,体动成史;

四维是史,史动????

现在人类企图理解第五维度。

而小度现在是第五维度的一位智者。一天,小度发现人类的许多科学家在试图理解第五维度,人类是四维生物,若是他们理解了第五维度,很可能也会到来第五维度的空间,这显然是小度不愿意看到的(毕竟哪里都有人口数量的问题….)所以小度希望他们尽可能晚的理解第五维度,因此,小度用更高维度的视角把所有人类中在理解第五维的科学家都看到了,而这些科学家的智商会不一样,所以他们的理解速度 Vi​ 也会不一样;并且,他们开始理解的时间点 Si​ 也不一样。理解速度 Vi​ 描述为每过单位时间可获得 Vi​ 个单位理解力,也就是说在 Si​+1 的时间点该科学家会第一次贡献 Vi​ 的理解力。我们定义理解力总数超过m 时理解了第五维度。 小度因为维度更高,可以使用时间悖论来给人类一次重大的打击,小度可以让任意一位科学家在任意一个时间点消失,所以他接下来的理解不会继续;而且人类不会记得他,所以他之前的贡献会消失。因为小度能力有限,所以小度只能使用一次暂时悖论。

现在求在尽可能晚的情况下,人类理解第五维度的最早时间点。

时间点初始为00,但显然,没有科学家能够在 00 时刻有贡献。

格式

输入格式:

第一行给出一个整数 n 和一个整数 m ,表示有 n 个科学家,在理解力总数超过 m 时理解了第五维度;
第二至 n+1 行:每行两个整数Si​ 和 Vi​;
对于 100% 的数据:1≤n≤10^5,m≤2∗10^9;
对于 100% 的数据:00≤Si​≤2∗10^9,0≤Vi​≤10^3。

输出格式:

一行,包含一个整数 T 表示在尽可能晚的情况下,人类理解第五维度的最早时间点。
若是人类永远无法理解第五维度,则输出-1。

 

题解

 

#include<bits/stdc++.h> using namespace std;
long long s[100000],v[100000],n,m;
bool check(int t){long long sum=0,maxn=-1;for(int i=1;i<=n;i++){if(t-s[i]<=0) continue;sum+=(t-s[i])*v[i];maxn=max(maxn,(t-s[i])*v[i]);}return sum-maxn>m;
}
int main( )
{cin>>n>>m;for(int i=1;i<=n;i++){cin>>s[i]>>v[i];}int l=0,r=999999999;while(l<r){int mid=(l+r)/2;if(check(mid)) r=mid;else l=mid+1;}if(check(1)) cout<<l;else cout<<-1;return 0;
}

执行结果: 

相关文章:

贪心算法的思路和典型例题

一、贪心算法的思想 贪心算法是一种求解问题时&#xff0c;总是做出在当前看来是最好的选择&#xff0c;不从整体最优上加以考虑的算法。 二.用贪心算法的解题策略 其基本思路是从问题的某一个初始解出发一步一步地进行&#xff0c;根据某个优化测度&#xff0c;每一步都要确保…...

演讲笔记|《一个ppt者的成长故事》

前言&#xff1a;本文为《说服力&#xff1a;工作型PPT该这样做》作者、秋叶PPT团队成员秦阳于2017年1月15日在北京望界无界空间的演讲内容要点总结。 1. 结构化思考&#xff08;思考能力&#xff09; 体系&#xff1a;挖多个坑&#xff0c;多个视角&#xff08;构建体系 – 获…...

【八大经典排序算法】堆排序

【八大经典排序算法】堆排序 一、概述二、思路解读三、代码实现&#xff08;大堆为例&#xff09; 一、概述 堆排序是J.W.J. Williams于1964年提出的。他提出了一种利用堆的数据结构进行排序的算法&#xff0c;并将其称为堆排序。堆排序是基于选择排序的一种改进&#xff0c;通…...

Redis五大基本数据类型

1、字符串类型 字符串类型相当于 java 中的 String 类型。Redis 中的 String 类型以二进制方式存储&#xff0c;不会做任何的编码转换&#xff0c;因此不仅仅可以存储文本数据、整数、普通的字符串、JSON、xml文件&#xff0c;还可以存储图片、视频、音频。String 存储的种类虽…...

AI一点通: OpenAI whisper 在线怎么调用,怎么同时输出时间信息?

OpenAI 语音转文字 whisper API提供了两个端点&#xff0c;即转录和翻译&#xff0c;这基于我们最先进的开源大型v2 Whisper模型。它们可以用来&#xff1a; 将音频转录成音频所在的语言。 翻译并将音频转录成英文。 文件上传目前限制为25 MB&#xff0c;支持以下输入文件类型…...

OpenText EnCase Mobile Investigator 查看、分析和报告被调查手机的证据

OpenText EnCase Mobile Investigator 查看、分析和报告被调查手机的证据 全球83.72%的人口拥有智能手机 OpenText™ EnCase™ Mobile Investigator 使调查人员能够轻松分析、审查和报告与其案件相关的移动设备上的证据。 为什么选择OpenText EnCase Mobile Investigator 预算友…...

【JavaScript】video标签配置及相关事件:

文章目录 一、标签配置&#xff1a;二、事件&#xff1a;三、案例&#xff1a; 一、标签配置&#xff1a; 标签名描述src要播放的路径地址autoplay是否自动播放&#xff0c;默认值是false,&#xff08;Boolean&#xff09;loop是否循环播放&#xff0c;默认值是false,&#xf…...

SpringSecurity 初始化解析

文章目录 前言加载SpringSecurity配置解析配置SpringSecurity 解析器security:http 解析FilterChainProxy的注册过程创建 SpringSecurity 过滤器总结 前言 通过上文分析知道了SpringSecurity对一个请求的具体处理流程。不知道大家是否跟我一样都有几个疑问&#xff1a; Filte…...

ip netns网络空间使用

SNAT 源地址转发 执行ip netns exec route_br_ens192_0 iptables -nL POSTROUTING -t nat --line-numbers 输出如下&#xff1a; Chain POSTROUTING (policy ACCEPT) num target prot opt source destination 1 SNAT all -- 0.0.0.0/…...

解决 Cannot read property ‘key‘ of undefined

目录 问题解决1解决2最终 问题 现场环境分页查询某些条件项查询时&#xff0c;分页接口获取成功但是数据不渲染&#xff0c;页面像是卡住了&#xff1a; 报错 Cannot read property key of undefined 解决1 有人说 使用的el-pagination在格式化代码的时候layout属性的参数会多加…...

「聊设计模式」之工厂方法模式(Factory Method)

&#x1f3c6;本文收录于《聊设计模式》专栏&#xff0c;专门攻坚指数级提升&#xff0c;助你一臂之力&#xff0c;早日登顶&#x1f680;&#xff0c;欢迎持续关注&&收藏&&订阅&#xff01; 前言 设计模式是指在软件设计中&#xff0c;经过总结和提炼的&#…...

局部变量,全局变量与内存

本文会使用IDA分析局部变量&#xff0c;全局变量在内存的存储 目录 使用IDA分析局部变量 使用IDA分析全局变量 总结 使用IDA分析局部变量 #include <stdio.h>int main() {int nNum 1;float fNum 2.5;char ch A;printf("int %d, float %f, char %c", nNu…...

Python爬虫异常处理实用技巧分享

当我们编写爬虫程序时&#xff0c;经常会遇到各种各样的异常情况&#xff0c;比如网络连接失败、页面解析错误、请求被拒绝等等。这些异常情况可能导致程序中断或者无法正常运行&#xff0c;给我们的数据采集工作带来一定的困扰。所以&#xff0c;掌握一些实用的异常处理技巧对…...

【性能测试】Jmeter —— jmeter计数器

jmeter计数器 如果需要引用的数据量较大&#xff0c;且要求不能重复或者需要递增&#xff0c;那么可以使用计数器来实现 如&#xff1a;新增功能&#xff0c;要求名称不能重复 1&#xff0c;新增计数器 计数器&#xff1a;允许用户创建一个在线程组之内都可以被引用的计数器…...

Python 布尔类型和比较运算符

视频版教程 Python3零基础7天入门实战视频教程 布尔( bool&#xff09;表达现实生活中的逻辑&#xff0c;即真和假&#xff0c;True表示真&#xff0c;False表示假。 实例&#xff1a; # 布尔类型定义 b1 True b2 False print(f"b1{b1},类型是{type(b1)}") prin…...

蓝牙核心规范(V5.4)10.1-BLE 入门笔记(1)

ble 规范 深入了解蓝牙LE需要熟悉相关的规格。蓝牙LE的架构、程序和协议由一项关键规范完全定义,称为蓝牙核心规范。产品如何使用蓝牙以实现互操作性由两种特殊类型称为配置文件和服务的规范集合所涵盖。图1展示了BLE规范类型及其相互关系。 1.1 蓝牙核心规范 蓝牙核心规范是…...

Java高级之泛型、自定义泛型、通配符的使用

泛型与File 文章目录 一、为什么要有泛型&#xff1f;1.1、什么是泛型&#xff1f;1.2、泛型的设计背景1.3、泛型的概念 二、在集合中使用泛型三、自定义泛型结构2.1、泛型方法的使用 四、泛型在继承上的体现五、通配符的使用5.1、通配符的使用5.2、有限制条件的通配符的使用 …...

代码随想录二刷day32

提示&#xff1a;文章写完后&#xff0c;目录可以自动生成&#xff0c;如何生成可参考右边的帮助文档 文章目录 前言一、力扣122. 买卖股票的最佳时机 II二、力扣55. 跳跃游戏三、力扣45. 跳跃游戏 II 前言 一、力扣122. 买卖股票的最佳时机 II class Solution {public int ma…...

linux基础篇

文章目录 linux基础篇1.Linux文件系统结构:2.常用的Linux指令&#xff1a;3.Shell指令&#xff1a;4.Linux服务管理&#xff1a;5.Linux磁盘挂载&#xff1a;其他 linux基础篇 1.Linux文件系统结构: 根目录 /bin目录&#xff1a;二进制可执行文件存放处boot目录&#xff1a;启…...

文心一言插件开发全流程,ERNIE-Bot-SDK可以调用文心一言的能力

文心一言插件开发 前言插件插件是什么工作原理申请开发权限 开始第一步&#xff1a;安装python第二步&#xff1a;搭建项目manifest 描述文件&#xff1a;ai-plugin.json插件服务描述文件&#xff1a;openapi.yaml开发自己的plugin-server 第三步&#xff1a;上传插件 SDK相关链…...

stm32G473的flash模式是单bank还是双bank?

今天突然有人stm32G473的flash模式是单bank还是双bank&#xff1f;由于时间太久&#xff0c;我真忘记了。搜搜发现&#xff0c;还真有人和我一样。见下面的链接&#xff1a;https://shequ.stmicroelectronics.cn/forum.php?modviewthread&tid644563 根据STM32G4系列参考手…...

day52 ResNet18 CBAM

在深度学习的旅程中&#xff0c;我们不断探索如何提升模型的性能。今天&#xff0c;我将分享我在 ResNet18 模型中插入 CBAM&#xff08;Convolutional Block Attention Module&#xff09;模块&#xff0c;并采用分阶段微调策略的实践过程。通过这个过程&#xff0c;我不仅提升…...

linux arm系统烧录

1、打开瑞芯微程序 2、按住linux arm 的 recover按键 插入电源 3、当瑞芯微检测到有设备 4、松开recover按键 5、选择升级固件 6、点击固件选择本地刷机的linux arm 镜像 7、点击升级 &#xff08;忘了有没有这步了 估计有&#xff09; 刷机程序 和 镜像 就不提供了。要刷的时…...

剑指offer20_链表中环的入口节点

链表中环的入口节点 给定一个链表&#xff0c;若其中包含环&#xff0c;则输出环的入口节点。 若其中不包含环&#xff0c;则输出null。 数据范围 节点 val 值取值范围 [ 1 , 1000 ] [1,1000] [1,1000]。 节点 val 值各不相同。 链表长度 [ 0 , 500 ] [0,500] [0,500]。 …...

基于matlab策略迭代和值迭代法的动态规划

经典的基于策略迭代和值迭代法的动态规划matlab代码&#xff0c;实现机器人的最优运输 Dynamic-Programming-master/Environment.pdf , 104724 Dynamic-Programming-master/README.md , 506 Dynamic-Programming-master/generalizedPolicyIteration.m , 1970 Dynamic-Programm…...

关于uniapp展示PDF的解决方案

在 UniApp 的 H5 环境中使用 pdf-vue3 组件可以实现完整的 PDF 预览功能。以下是详细实现步骤和注意事项&#xff1a; 一、安装依赖 安装 pdf-vue3 和 PDF.js 核心库&#xff1a; npm install pdf-vue3 pdfjs-dist二、基本使用示例 <template><view class"con…...

Linux系统部署KES

1、安装准备 1.版本说明V008R006C009B0014 V008&#xff1a;是version产品的大版本。 R006&#xff1a;是release产品特性版本。 C009&#xff1a;是通用版 B0014&#xff1a;是build开发过程中的构建版本2.硬件要求 #安全版和企业版 内存&#xff1a;1GB 以上 硬盘&#xf…...

0x-3-Oracle 23 ai-sqlcl 25.1 集成安装-配置和优化

是不是受够了安装了oracle database之后sqlplus的简陋&#xff0c;无法删除无法上下翻页的苦恼。 可以安装readline和rlwrap插件的话&#xff0c;配置.bahs_profile后也能解决上下翻页这些&#xff0c;但是很多生产环境无法安装rpm包。 oracle提供了sqlcl免费许可&#xff0c…...

【UE5 C++】通过文件对话框获取选择文件的路径

目录 效果 步骤 源码 效果 步骤 1. 在“xxx.Build.cs”中添加需要使用的模块 &#xff0c;这里主要使用“DesktopPlatform”模块 2. 添加后闭UE编辑器&#xff0c;右键点击 .uproject 文件&#xff0c;选择 "Generate Visual Studio project files"&#xff0c;重…...

如何把工业通信协议转换成http websocket

1.现状 工业通信协议多数工作在边缘设备上&#xff0c;比如&#xff1a;PLC、IOT盒子等。上层业务系统需要根据不同的工业协议做对应开发&#xff0c;当设备上用的是modbus从站时&#xff0c;采集设备数据需要开发modbus主站&#xff1b;当设备上用的是西门子PN协议时&#xf…...