POJ 3045 Cow Acrobats 二分+优先队列
一、题目大意
题目中给出了N头牛,这些牛要互相叠罗汉,牛i承担的风险risk[i]为牛i上面的牛的质量之和sum[i](如果上面没有牛就是0)减去牛i的力量strength[i],即risk[i]=sum[i]-strength[i]
我们要优化这个叠罗汉的顺序,使得1-N头牛的风险值中的最大值,最小。
二、解题思路
这个题目要对风险值进行二分
首先我们设牛i的质量为weight[i],牛i的力量为strength[i],风险值为mid,所有牛的质量之和为sum,按叠罗汉顺序从下往上数最底下一头牛为first,倒数第二头牛为second,第三个为third,那么有如下表达式。
sum-weight[first]-strength[first]<=mid
sum-weight[first]-weight[second]-strength[second]<=mid
sum-weight[first]-weight[second]-weight[third]-strength[third]<=mid
不难看出,我们让顺序靠下的牛在满足条件的情况下,质量尽可能大,那么就缓解了顺序靠上的牛的压力。
所以题目对风险值进行二分,然后判断风险值是否可行,如果可行,则缩小风险值,如果不可行,则放大风险值,输出最后一次满足条件的风险值即可。
判断的过程的思路来自于上面的表达式,如果我们让底下的牛的质量尽可能大,那么对顶上的牛的力量的要求就不会那么严苛。判断过程中进行N次循环,每次找到满足 当前剩余牛的重量-牛i的重量-牛i的力量<=mid 条件的所有牛i,放入到优先队列中,取出质量最大的放在底下,同时更新剩余牛的重量,然后继续下次循环,如果优先队列为空了,那么代表我们找不到满足条件的牛i,则mid过小,返回false,N次循环正常结束,则mid可行。(需要注意的是要避免优先队列放入重复的元素)
三、代码
代码这里为了防止中途计算溢出,对mid开了一个long long,对于本题目的数据其实可以不开。
#include <iostream>
#include <algorithm>
#include <queue>
using namespace std;
typedef long long ll;
struct Cow
{int weight, strength;Cow(int weight = 0, int strength = 0) : weight(weight), strength(strength) {}
};
int N;
Cow cows[50007];
int inf = 0x3f3f3f3f, weightSum = 0;
bool operator<(const Cow &a, const Cow &b)
{return a.weight < b.weight;
}
bool compare(const Cow &a, const Cow &b)
{return (a.strength + a.weight) < (b.strength + b.weight);
}
void input()
{scanf("%d", &N);for (int i = 0; i < N; i++){scanf("%d%d", &cows[i].weight, &cows[i].strength);weightSum += cows[i].weight;}sort(cows, cows + N, compare);cows[N] = Cow(0, inf);
}
// 判断最小风险mid是否可行
bool judge(int mid)
{priority_queue<Cow> que;int right = N, currentSum = weightSum;for (int i = 0; i < N; i++){int next = lower_bound(cows, cows + N + 1, Cow(currentSum - mid, 0), compare) - cows;for (int j = next; j < right; j++){que.push(cows[j]);}right = next;if (que.empty()){return false;}Cow cow = que.top();que.pop();currentSum -= cow.weight;}return true;
}
void binarySearch()
{int left = -1000000001, right = weightSum;while (left + 1 < right){ll mid = left;mid += right;mid = mid >> 1;if (judge((int)mid)){right = (int)mid;}else{left = (int)mid;}}printf("%d\n", right);
}
int main()
{input();binarySearch();return 0;
}
相关文章:
POJ 3045 Cow Acrobats 二分+优先队列
一、题目大意 题目中给出了N头牛,这些牛要互相叠罗汉,牛i承担的风险risk[i]为牛i上面的牛的质量之和sum[i](如果上面没有牛就是0)减去牛i的力量strength[i],即risk[i]sum[i]-strength[i] 我们要优化这个叠罗汉的顺序…...
手写实现call() apply() bind()函数,附有详细注释,包含this指向、arguments讲解
手写实现call() apply() bind()函数是很经典的问题,但是能掰扯清楚的文章确实不算多,于是笔者才决定写下本文,希望能给读者带来一些启发,如有错误欢迎指正。 目录 补充知识 函数中的this指向 类数组对象arguments call() 原理…...
MySQL中日期、时间直接相减的坑
前言 在牛客网上写一道 SQL 题时,需要计算两个日期之间相隔的秒数,我在写的时候直接将两个日期进行相减,得出来的值却不是相差的秒数。 情景再现 我在 MySQL 中进行了测试,得出的结论是:如果日期类型直接相减&#…...
漏洞发现-web应用发现探针类型利用(43)
关于在真实环境下面,这个漏洞该如何发现 这里老师把它分成了三块第一类是 #已知cms 如常见的dedecms,discuz,wordpress等源码结构,这些都是网上比较知名的php源码的cms的名称,这是我们在国内常见的几个程序…...
专门针对开发人员,攻击者利用Rust获取操作系统信息
近日,研究人员在 Rust 编程语言的 crate 注册表中发现了一些恶意软件包,专门针对开发人员。 Phylum 在上周发布的一份报告中称,这些库是由一个名为 "amaperf "的用户在 2023 年 8 月 14 日至 16 日之间上传的。现已删除的软件包名…...
PHP8的箭头函数-PHP8知识详解
php 7.4 引入了箭头函数(Arrow Functions),并在 PHP 8 中得到了进一步改进和扩展。 箭头函数是一种更简洁的匿名函数形式,它们提供了一种更便捷的方式来定义轻量级的、单行的回调函数。 箭头函数的语法如下: fn (参…...
初识PHP编程:探索Web开发的起点
初识PHP编程:探索Web开发的起点 PHP(Hypertext Preprocessor)是一种广泛使用的服务器端脚本语言,专门用于Web开发。它的强大功能和简单易学的语法使得它成为初学者和专业开发者的首选。在本文中,我们将探索什么是PHP&…...
Git——Windows平台创建gitee私有仓库详解
目录 1. 安装git 2. gitbash配置 2.1 设置 2.2 生成key 2.3 项目管理 2.3.1 本地新建 2.3.2 clone远程仓库的工程到本地改文件 1. 安装git 默认安装。 2. gitbash配置 2.1 设置 打开gitbash,设置用户名和邮箱: git config --global user.name …...
Git基础教程-常用命令整理:学会Git使用方法和错误解决
目录 一、了解Git的基本概念 二、Git的安装和配置 Git的安装 Git的配置 用户信息 文本编辑器 差异分析工具 查看配置信息 三、Git的基本操作 基本原理 基本操作命令 基本操作示例 场景一:创建新仓库 场景二:拉取并编辑远程仓库 四、常见问…...
Ops实践 | 国产化KylinOS系统中快速部署企业内部高性能DNS服务器、时间同步服务器 (精选)...
各位看友,由于微信公众号推送机制改变,现在需要设置为星标才能收到的本公众号推送消息哟。关注回复【学习交流群】加入【安全开发运维】答疑交流群 请朋友们【多多点击文中的广告】,支持作者更新更多文章。 目录: 本文为作者原创文章…...
stm32之IIC协议
主要通过两个层面来讲:物理层、协议层。 IIC是一个同步半双工串行总线协议。 一、物理层(通信模型) 1、最早是飞利浦公司开发的这个协议,最早应用到其产品上去。 2、两线制(两根信号线) 其中SCL为时钟…...
范式 事务 多表查询
范式 概念:设计数据库时,需要遵循的一些规范。要遵循后边的范式要求,必须遵循前边的所有范式要求 第一范式: 数据库表的每一列都是不可分割的基本数据项 这样子就不满足第一范式 这样子就满足第一范式 存在问题: 数…...
基于白鲸算法优化的BP神经网络(预测应用) - 附代码
基于白鲸算法优化的BP神经网络(预测应用) - 附代码 文章目录 基于白鲸算法优化的BP神经网络(预测应用) - 附代码1.数据介绍2.白鲸优化BP神经网络2.1 BP神经网络参数设置2.2 白鲸算法应用 4.测试结果:5.Matlab代码 摘要…...
java并发编程 ReentrantLock详解
文章目录 1 概要2 相关文章3 例子4 方法详解4.1 lock()4.2 unlock()4.3 tryLock()4.4 其他公平锁 总结 1 概要 ReentrantLock 通过实现Lock接口的行为,提供锁机制。但是实现委托给了内部的Sync,Sync extends AbstractQueuedSynchronizer,继承…...
Java获取文件内容IO流
文章目录 InputStream和ReaderScannerNIO外传 一般读取文件类的使用字符流即可 InputStream和Reader InputStream和Reader是Java IO中的两个重要的抽象基类,InputStream是二进制流,Reader是字符流。使用InputStream或者Reader读取文件内容可以帮助我们…...
Java后端开发面试题——集合篇
ArrayList底层的实现原理是什么 底层数据结构 ArrayList底层是用动态的数组实现的 初始容量 ArrayList初始容量为0,当第一次添加数据的时候才会初始化容量为10 扩容逻辑 ArrayList在进行扩容的时候是原来容量的1.5倍,每次扩容都需要拷贝数组 添加逻…...
如何允许远程访问MySQL
许多网站和应用程序一开始都将web服务器和数据库后端托管在同一台机器上。不过,随着时间的推移,这样的设置可能会变得繁琐和难以扩展。一种常见的解决方案是通过设置远程数据库来分离这些功能,允许服务器和数据库在各自的机器上按自己的速度增…...
001图机器学习与图神经网络简介
文章目录 一. 无处不在的图二. 如何对图数据做信息挖掘三. 图神经网络四. 图机器学习常用的编程工具五. 图的可视化工具六. 常见的图数据库七. 图机器学习的应用举例八. 结束语 一. 无处不在的图 一切具有关联关系的数据都可以用图来表示。比如:交通网、知识图谱、…...
万级数据优化EasyExcel+mybatis流式查询导出封装
文章目录 前言.万级数据优化一. 直接上流式查询封装工具代码二. 传统分页导出查询三. 流式查询概念游标查询 前言.万级数据优化 我们不妨先给大家讲一个概念,利用此概念我们正好给大家介绍一个数据库优化的小技巧: 需求如下:将一个地市表的数…...
Unity——脚本序列化
在介绍序列化之前,我们先来了解一下为什么要对数据进行序列化 数据序列化有以下几个主要的应用场景和目的: 1. 持久化存储:序列化可以将对象或数据结构转换为字节序列,使得其可以被存储在磁盘上或数据库中。通过序列化ÿ…...
JavaSec-RCE
简介 RCE(Remote Code Execution),可以分为:命令注入(Command Injection)、代码注入(Code Injection) 代码注入 1.漏洞场景:Groovy代码注入 Groovy是一种基于JVM的动态语言,语法简洁,支持闭包、动态类型和Java互操作性,…...
TDengine 快速体验(Docker 镜像方式)
简介 TDengine 可以通过安装包、Docker 镜像 及云服务快速体验 TDengine 的功能,本节首先介绍如何通过 Docker 快速体验 TDengine,然后介绍如何在 Docker 环境下体验 TDengine 的写入和查询功能。如果你不熟悉 Docker,请使用 安装包的方式快…...
golang循环变量捕获问题
在 Go 语言中,当在循环中启动协程(goroutine)时,如果在协程闭包中直接引用循环变量,可能会遇到一个常见的陷阱 - 循环变量捕获问题。让我详细解释一下: 问题背景 看这个代码片段: fo…...
遍历 Map 类型集合的方法汇总
1 方法一 先用方法 keySet() 获取集合中的所有键。再通过 gey(key) 方法用对应键获取值 import java.util.HashMap; import java.util.Set;public class Test {public static void main(String[] args) {HashMap hashMap new HashMap();hashMap.put("语文",99);has…...
PPT|230页| 制造集团企业供应链端到端的数字化解决方案:从需求到结算的全链路业务闭环构建
制造业采购供应链管理是企业运营的核心环节,供应链协同管理在供应链上下游企业之间建立紧密的合作关系,通过信息共享、资源整合、业务协同等方式,实现供应链的全面管理和优化,提高供应链的效率和透明度,降低供应链的成…...
转转集团旗下首家二手多品类循环仓店“超级转转”开业
6月9日,国内领先的循环经济企业转转集团旗下首家二手多品类循环仓店“超级转转”正式开业。 转转集团创始人兼CEO黄炜、转转循环时尚发起人朱珠、转转集团COO兼红布林CEO胡伟琨、王府井集团副总裁祝捷等出席了开业剪彩仪式。 据「TMT星球」了解,“超级…...
【项目实战】通过多模态+LangGraph实现PPT生成助手
PPT自动生成系统 基于LangGraph的PPT自动生成系统,可以将Markdown文档自动转换为PPT演示文稿。 功能特点 Markdown解析:自动解析Markdown文档结构PPT模板分析:分析PPT模板的布局和风格智能布局决策:匹配内容与合适的PPT布局自动…...
DIY|Mac 搭建 ESP-IDF 开发环境及编译小智 AI
前一阵子在百度 AI 开发者大会上,看到基于小智 AI DIY 玩具的演示,感觉有点意思,想着自己也来试试。 如果只是想烧录现成的固件,乐鑫官方除了提供了 Windows 版本的 Flash 下载工具 之外,还提供了基于网页版的 ESP LA…...
论文浅尝 | 基于判别指令微调生成式大语言模型的知识图谱补全方法(ISWC2024)
笔记整理:刘治强,浙江大学硕士生,研究方向为知识图谱表示学习,大语言模型 论文链接:http://arxiv.org/abs/2407.16127 发表会议:ISWC 2024 1. 动机 传统的知识图谱补全(KGC)模型通过…...
鱼香ros docker配置镜像报错:https://registry-1.docker.io/v2/
使用鱼香ros一件安装docker时的https://registry-1.docker.io/v2/问题 一键安装指令 wget http://fishros.com/install -O fishros && . fishros出现问题:docker pull 失败 网络不同,需要使用镜像源 按照如下步骤操作 sudo vi /etc/docker/dae…...
