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

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头牛&#xff0c;这些牛要互相叠罗汉&#xff0c;牛i承担的风险risk[i]为牛i上面的牛的质量之和sum[i]&#xff08;如果上面没有牛就是0&#xff09;减去牛i的力量strength[i]&#xff0c;即risk[i]sum[i]-strength[i] 我们要优化这个叠罗汉的顺序…...

手写实现call() apply() bind()函数,附有详细注释,包含this指向、arguments讲解

手写实现call() apply() bind()函数是很经典的问题&#xff0c;但是能掰扯清楚的文章确实不算多&#xff0c;于是笔者才决定写下本文&#xff0c;希望能给读者带来一些启发&#xff0c;如有错误欢迎指正。 目录 补充知识 函数中的this指向 类数组对象arguments call() 原理…...

MySQL中日期、时间直接相减的坑

前言 在牛客网上写一道 SQL 题时&#xff0c;需要计算两个日期之间相隔的秒数&#xff0c;我在写的时候直接将两个日期进行相减&#xff0c;得出来的值却不是相差的秒数。 情景再现 我在 MySQL 中进行了测试&#xff0c;得出的结论是&#xff1a;如果日期类型直接相减&#…...

漏洞发现-web应用发现探针类型利用(43)

关于在真实环境下面&#xff0c;这个漏洞该如何发现 这里老师把它分成了三块第一类是 #已知cms 如常见的dedecms&#xff0c;discuz&#xff0c;wordpress等源码结构&#xff0c;这些都是网上比较知名的php源码的cms的名称&#xff0c;这是我们在国内常见的几个程序&#xf…...

专门针对开发人员,攻击者利用Rust获取操作系统信息

近日&#xff0c;研究人员在 Rust 编程语言的 crate 注册表中发现了一些恶意软件包&#xff0c;专门针对开发人员。 Phylum 在上周发布的一份报告中称&#xff0c;这些库是由一个名为 "amaperf "的用户在 2023 年 8 月 14 日至 16 日之间上传的。现已删除的软件包名…...

PHP8的箭头函数-PHP8知识详解

php 7.4 引入了箭头函数&#xff08;Arrow Functions&#xff09;&#xff0c;并在 PHP 8 中得到了进一步改进和扩展。 箭头函数是一种更简洁的匿名函数形式&#xff0c;它们提供了一种更便捷的方式来定义轻量级的、单行的回调函数。 箭头函数的语法如下&#xff1a; fn (参…...

初识PHP编程:探索Web开发的起点

初识PHP编程&#xff1a;探索Web开发的起点 PHP&#xff08;Hypertext Preprocessor&#xff09;是一种广泛使用的服务器端脚本语言&#xff0c;专门用于Web开发。它的强大功能和简单易学的语法使得它成为初学者和专业开发者的首选。在本文中&#xff0c;我们将探索什么是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&#xff0c;设置用户名和邮箱&#xff1a; git config --global user.name …...

Git基础教程-常用命令整理:学会Git使用方法和错误解决

目录 一、了解Git的基本概念 二、Git的安装和配置 Git的安装 Git的配置 用户信息 文本编辑器 差异分析工具 查看配置信息 三、Git的基本操作 基本原理 基本操作命令 基本操作示例 场景一&#xff1a;创建新仓库 场景二&#xff1a;拉取并编辑远程仓库 四、常见问…...

Ops实践 | 国产化KylinOS系统中快速部署企业内部高性能DNS服务器、时间同步服务器 (精选)...

各位看友&#xff0c;由于微信公众号推送机制改变&#xff0c;现在需要设置为星标才能收到的本公众号推送消息哟。关注回复【学习交流群】加入【安全开发运维】答疑交流群 请朋友们【多多点击文中的广告】&#xff0c;支持作者更新更多文章。 目录: 本文为作者原创文章&#xf…...

stm32之IIC协议

主要通过两个层面来讲&#xff1a;物理层、协议层。 IIC是一个同步半双工串行总线协议。 一、物理层&#xff08;通信模型&#xff09; 1、最早是飞利浦公司开发的这个协议&#xff0c;最早应用到其产品上去。 2、两线制&#xff08;两根信号线&#xff09; 其中SCL为时钟…...

范式 事务 多表查询

范式 概念&#xff1a;设计数据库时&#xff0c;需要遵循的一些规范。要遵循后边的范式要求&#xff0c;必须遵循前边的所有范式要求 第一范式&#xff1a; 数据库表的每一列都是不可分割的基本数据项 这样子就不满足第一范式 这样子就满足第一范式 存在问题&#xff1a; 数…...

基于白鲸算法优化的BP神经网络(预测应用) - 附代码

基于白鲸算法优化的BP神经网络&#xff08;预测应用&#xff09; - 附代码 文章目录 基于白鲸算法优化的BP神经网络&#xff08;预测应用&#xff09; - 附代码1.数据介绍2.白鲸优化BP神经网络2.1 BP神经网络参数设置2.2 白鲸算法应用 4.测试结果&#xff1a;5.Matlab代码 摘要…...

java并发编程 ReentrantLock详解

文章目录 1 概要2 相关文章3 例子4 方法详解4.1 lock()4.2 unlock()4.3 tryLock()4.4 其他公平锁 总结 1 概要 ReentrantLock 通过实现Lock接口的行为&#xff0c;提供锁机制。但是实现委托给了内部的Sync&#xff0c;Sync extends AbstractQueuedSynchronizer&#xff0c;继承…...

Java获取文件内容IO流

文章目录 InputStream和ReaderScannerNIO外传 一般读取文件类的使用字符流即可 InputStream和Reader InputStream和Reader是Java IO中的两个重要的抽象基类&#xff0c;InputStream是二进制流&#xff0c;Reader是字符流。使用InputStream或者Reader读取文件内容可以帮助我们…...

Java后端开发面试题——集合篇

ArrayList底层的实现原理是什么 底层数据结构 ArrayList底层是用动态的数组实现的 初始容量 ArrayList初始容量为0&#xff0c;当第一次添加数据的时候才会初始化容量为10 扩容逻辑 ArrayList在进行扩容的时候是原来容量的1.5倍&#xff0c;每次扩容都需要拷贝数组 添加逻…...

如何允许远程访问MySQL

许多网站和应用程序一开始都将web服务器和数据库后端托管在同一台机器上。不过&#xff0c;随着时间的推移&#xff0c;这样的设置可能会变得繁琐和难以扩展。一种常见的解决方案是通过设置远程数据库来分离这些功能&#xff0c;允许服务器和数据库在各自的机器上按自己的速度增…...

001图机器学习与图神经网络简介

文章目录 一. 无处不在的图二. 如何对图数据做信息挖掘三. 图神经网络四. 图机器学习常用的编程工具五. 图的可视化工具六. 常见的图数据库七. 图机器学习的应用举例八. 结束语 一. 无处不在的图 一切具有关联关系的数据都可以用图来表示。比如&#xff1a;交通网、知识图谱、…...

万级数据优化EasyExcel+mybatis流式查询导出封装

文章目录 前言.万级数据优化一. 直接上流式查询封装工具代码二. 传统分页导出查询三. 流式查询概念游标查询 前言.万级数据优化 我们不妨先给大家讲一个概念&#xff0c;利用此概念我们正好给大家介绍一个数据库优化的小技巧&#xff1a; 需求如下&#xff1a;将一个地市表的数…...

Unity——脚本序列化

在介绍序列化之前&#xff0c;我们先来了解一下为什么要对数据进行序列化 数据序列化有以下几个主要的应用场景和目的&#xff1a; 1. 持久化存储&#xff1a;序列化可以将对象或数据结构转换为字节序列&#xff0c;使得其可以被存储在磁盘上或数据库中。通过序列化&#xff…...

2.Vue编写一个app

1.src中重要的组成 1.1main.ts // 引入createApp用于创建应用 import { createApp } from "vue"; // 引用App根组件 import App from ./App.vue;createApp(App).mount(#app)1.2 App.vue 其中要写三种标签 <template> <!--html--> </template>…...

江苏艾立泰跨国资源接力:废料变黄金的绿色供应链革命

在华东塑料包装行业面临限塑令深度调整的背景下&#xff0c;江苏艾立泰以一场跨国资源接力的创新实践&#xff0c;重新定义了绿色供应链的边界。 跨国回收网络&#xff1a;废料变黄金的全球棋局 艾立泰在欧洲、东南亚建立再生塑料回收点&#xff0c;将海外废弃包装箱通过标准…...

PL0语法,分析器实现!

简介 PL/0 是一种简单的编程语言,通常用于教学编译原理。它的语法结构清晰,功能包括常量定义、变量声明、过程(子程序)定义以及基本的控制结构(如条件语句和循环语句)。 PL/0 语法规范 PL/0 是一种教学用的小型编程语言,由 Niklaus Wirth 设计,用于展示编译原理的核…...

C# SqlSugar:依赖注入与仓储模式实践

C# SqlSugar&#xff1a;依赖注入与仓储模式实践 在 C# 的应用开发中&#xff0c;数据库操作是必不可少的环节。为了让数据访问层更加简洁、高效且易于维护&#xff0c;许多开发者会选择成熟的 ORM&#xff08;对象关系映射&#xff09;框架&#xff0c;SqlSugar 就是其中备受…...

windows系统MySQL安装文档

概览&#xff1a;本文讨论了MySQL的安装、使用过程中涉及的解压、配置、初始化、注册服务、启动、修改密码、登录、退出以及卸载等相关内容&#xff0c;为学习者提供全面的操作指导。关键要点包括&#xff1a; 解压 &#xff1a;下载完成后解压压缩包&#xff0c;得到MySQL 8.…...

Java求职者面试指南:Spring、Spring Boot、Spring MVC与MyBatis技术解析

Java求职者面试指南&#xff1a;Spring、Spring Boot、Spring MVC与MyBatis技术解析 一、第一轮基础概念问题 1. Spring框架的核心容器是什么&#xff1f;它的作用是什么&#xff1f; Spring框架的核心容器是IoC&#xff08;控制反转&#xff09;容器。它的主要作用是管理对…...

2025年低延迟业务DDoS防护全攻略:高可用架构与实战方案

一、延迟敏感行业面临的DDoS攻击新挑战 2025年&#xff0c;金融交易、实时竞技游戏、工业物联网等低延迟业务成为DDoS攻击的首要目标。攻击呈现三大特征&#xff1a; AI驱动的自适应攻击&#xff1a;攻击流量模拟真实用户行为&#xff0c;差异率低至0.5%&#xff0c;传统规则引…...

【大厂机试题解法笔记】矩阵匹配

题目 从一个 N * M&#xff08;N ≤ M&#xff09;的矩阵中选出 N 个数&#xff0c;任意两个数字不能在同一行或同一列&#xff0c;求选出来的 N 个数中第 K 大的数字的最小值是多少。 输入描述 输入矩阵要求&#xff1a;1 ≤ K ≤ N ≤ M ≤ 150 输入格式 N M K N*M矩阵 输…...

华为云Flexus+DeepSeek征文 | 基于Dify构建具备联网搜索能力的知识库问答助手

华为云FlexusDeepSeek征文 | 基于Dify构建具备联网搜索能力的知识库问答助手 一、构建知识库问答助手引言二、构建知识库问答助手环境2.1 基于FlexusX实例的Dify平台2.2 基于MaaS的模型API商用服务 三、构建知识库问答助手实战3.1 配置Dify环境3.2 创建知识库问答助手3.3 使用知…...

机器学习复习3--模型评估

误差与过拟合 我们将学习器对样本的实际预测结果与样本的真实值之间的差异称为&#xff1a;误差&#xff08;error&#xff09;。 误差定义&#xff1a; ①在训练集上的误差称为训练误差&#xff08;training error&#xff09;或经验误差&#xff08;empirical error&#x…...