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

Cow Acrobats ( 临项交换贪心 )

题目大意:

N 头牛 , 每头牛有一个重量(Weight)和一个力量(Strenth) , N头牛进行排列 , 第 i 头牛的风险值为其上所有牛总重减去自身力量 , 问如何排列可以使最大风险值最小 , 求出这个最小的最大风险值;

思路:临项交换

邻项交换排序是一种常见的贪心算法,通过比较两个相邻元素交换前后的优劣对整个序列进行排序,从而使得这个序列成为题目所求的最优解。

我们假设前 i 项已经是最优排列 , 且第 i + 1 项和第 i + 2 项当前排列时最优
在这里插入图片描述
那么对于第 i + 1 个
resi+1=sum−s2res_{i+1} = sum - s_2resi+1=sums2
对于第 i + 2 个
resi+2=sum+s1−w2res_{i+2} = sum + s_1 - w_2resi+2=sum+s1w2

若我们交换第 i + 1 项 和 第 i + 2 项
在这里插入图片描述

那么对于第 i + 1 个
resi+1′=sum−w2res_{i+1}'= sum - w_2resi+1=sumw2
对于第 i + 2 个
resi+2′=sum+w1−s2res_{i+2}' = sum + w_1 - s_2resi+2=sum+w1s2

在这里我们已经假设交换前为最优状态 , 所以我们根据题目中最大值最小的定义可以得到下面这个式子
max(resi+1,resi+2)<=max(resi+1′,resi+2′)max(res_{i+1} , res_{i+2}) <= max(res_{i+1}' , res_{i+2}')max(resi+1,resi+2)<=max(resi+1,resi+2)
转化一下
max(sum−s2,sum+s1−w2)<=max(sum−w2,sum+w1−s2)max(sum - s_2 , sum + s_1 - w_2) <= max(sum - w_2 , sum + w_1 - s_2)max(sums2,sum+s1w2)<=max(sumw2,sum+w1s2)
每一项 减去 sum 加上 (s2+w2s_2 + w_2s2+w2)
max(w2,s1+s2)<=max(s2,w1+w2)max(w_2 , s_1 + s_2) <= max(s_2 , w_1 + w_2)max(w2,s1+s2)<=max(s2,w1+w2)
至此 , 我们就推出了我们想要的交换方程

bool cmp(node a,node b){return max(a.x + a.y , b.y) < max(b.x + b.y , a.y) || (max(a.x + a.y , b.y) == max(b.x + b.y , a.y) && a.x + a.y < b.x + b.y); 
}

这里等于号要特判 ,不懂的可以看看下面这个博客
浅谈邻项交换排序的应用以及需要注意的问题

当我们排好序后 ,不要忘记我们的问题 , 是要求最小的最大值 ,这是只要遍历所有状态求出最大值即可。

#include<bits/stdc++.h>
using namespace std;
#define fi first
#define se second
#define IOS std::ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
typedef long long ll;
const int N = 2e5+10;
const int p = 1e9 + 7;
typedef pair<int,int>PII;
const int inf = 1 << 31 - 1;
const double eps = 1e-9;int n;struct node{int x,y;
}a[N];bool cmp(node a,node b){return max(a.x + a.y , b.y) < max(b.x + b.y , a.y) || (max(a.x + a.y , b.y) == max(b.x + b.y , a.y) && a.x + a.y < b.x + b.y); 
}int main(){IOScin >> n;for(int i=1;i<=n;i++){cin >> a[i].x >> a[i].y;}sort(a+1,a+1+n,cmp);int ans = -inf , sum = 0;for(int i=1;i<=n;i++){sum += a[i-1].x;ans = max(ans , sum - a[i].y);}cout << ans ;return 0;
}
//freopen("文件名.in","r",stdin);
//freopen("文件名.out","w",stdout);

相关文章:

Cow Acrobats ( 临项交换贪心 )

题目大意&#xff1a; N 头牛 &#xff0c; 每头牛有一个重量(Weight)和一个力量(Strenth) &#xff0c; N头牛进行排列 &#xff0c; 第 i 头牛的风险值为其上所有牛总重减去自身力量 &#xff0c; 问如何排列可以使最大风险值最小 &#xff0c; 求出这个最小的最大风险值&am…...

MySQL:为什么说应该优先选择普通索引,尽量避免使用唯一索引

前言 在使用MySQL的过程中&#xff0c;随着表数据的逐渐增多&#xff0c;为了更快的查询我们需要的数据&#xff0c;我们会在表中建立不同类型的索引。 今天我们来聊一聊&#xff0c;普通索引和唯一索引的使用场景&#xff0c; 以及为什么说推荐大家优先使用普通索引&#xf…...

Spring Cloud alibaba之Feign

JAVA项目中如何实现接口调用&#xff1f;HttpclientHttpclient是Apache Jakarta Common下的子项目&#xff0c;用来提供高效的、最新的、功能丰富的支持Http协议的客户端编程工具包&#xff0c;并且它支持HTTP协议最新版本和建议。HttpClient相比传统JDK自带的URL Connection&a…...

零信任-Google谷歌零信任介绍(3)

谷歌零信任的介绍&#xff1f; "Zero Trust" 是一种网络安全模型&#xff0c;旨在通过降低网络中的信任级别来防止安全威胁。在零信任模型中&#xff0c;不论请求来自内部网络还是外部网络&#xff0c;系统都将对所有请求进行详细的验证和审核。这意味着每次请求都需…...

Numpy基础——人工智能基础

文章目录一、Numpy概述1.优势2.numpy历史3.Numpy的核心&#xff1a;多维数组4.numpy基础4.1 ndarray数组4.2 内存中的ndarray对象一、Numpy概述 1.优势 Numpy(Nummerical Python),补充了Python语言所欠缺的数值计算能力&#xff1b;Numpy是其它数据分析及机器学习库的底层库&…...

电商仓储与配送云仓是什么?

仓库是整个供给链的关键局部。它们是产品暂停和触摸的点&#xff0c;耗费空间和时间(工时)。空间和时间反过来也是费用。经过开发数学和计算机模型来微调仓库的规划和操作&#xff0c;经理能够显著降低与产品分销相关的劳动力本钱&#xff0c;进步仓库空间应用率&#xff0c;并…...

【零基础入门前端系列】—HTML介绍(一)

【零基础入门前端系列】—HTML介绍&#xff08;一&#xff09; 一、什么是HTML HTML是用来描述网页的一种语言HTML指的是超文本标记语言&#xff1a;HyperText Markup LanguageHTML不是一种编程语言&#xff0c;而是一种超文本标记语言&#xff0c;标记语言是一套标记标签(ma…...

Elasticsearch索引库和文档的相关操作

前言&#xff1a;最近一直在复习Elasticsearch相关的知识&#xff0c;公司搜索相关的技术用到了这个&#xff0c;用公司电脑配了环境&#xff0c;借鉴网上的课程进行了总结。希望能够加深自己的印象以及帮助到其他的小伙伴儿们&#x1f609;&#x1f609;。 如果文章有什么需要…...

使用Python,Opencv检测图像,视频中的猫

使用Python&#xff0c;Opencv检测图像&#xff0c;视频中的猫&#x1f431; 这篇博客将介绍如何使用Python&#xff0c;OpenCV库附带的默认Haar级联检测器来检测图像中的猫。同样的技术也可以应用于视频流。这些哈尔级联由约瑟夫豪斯&#xff08;Joseph Howse&#xff09;训练…...

浅谈域名和服务器集约化管理的误区

一个正常的网站通常由域名、网站程序、服务器三个部分组成&#xff0c;网站程序由单位开发设计&#xff0c;而域名和服务器则需要租用购买&#xff0c;那么域名和服务器之间的关系是什么&#xff1f;如何实现域名和服务器的有效管理呢&#xff1f; 服务器和域名的关系 服务器…...

迪赛智慧数——柱状图(正负条形图):20212022人才求职最关注的因素

效果图从近两年职场跳槽方向看&#xff0c;相比此前人们对高薪大厂趋之若鹜&#xff0c;如今职场人更关注业务前景。根据相关数据显示&#xff0c;职场人求职最关注的因素中&#xff0c;“薪资福利”权重下降&#xff0c;“个人发展”权重上升&#xff0c;“业务前景”首次进入…...

网络安全-黑帽白帽红客与网络安全法

网络安全-黑帽白帽红客与网络安全法 本章内容较少&#xff0c;因为刚开端。 黑客来源于hacker 指的是信息安全里面&#xff0c;能够自由出入对方系统&#xff0c;指的是擅长IT技术的电脑高手 黑帽黑客-坏蛋&#xff0c;研究木马的&#xff0c;找漏洞的&#xff0c;攻击网络或者…...

Xpath元素定位之同级节点,父节点,子节点

XPath学习:轴(8)——following-siblingXPath 是一门在 XML 文档中查找信息的语言。XPath 可用来在 XML 文档中对元素和属性进行遍历。XPath 是 W3C XSLT 标准的主要元素&#xff0c;并且 XQuery 和 XPointer 同时被构建于 XPath 表达之上。推荐一个挺不错的网站&#xff1a;htt…...

华为OD机试 - 挑选字符串(Python)| 真题+思路+代码

挑选字符串 题目 给定 a-z,26 个英文字母小写字符串组成的字符串 A 和 B, 其中 A 可能存在重复字母,B 不会存在重复字母, 现从字符串 A 中按规则挑选一些字母可以组成字符串 B 挑选规则如下: 同一个位置的字母只能挑选一次, 被挑选字母的相对先后顺序不能被改变, 求最…...

python笔记-- “__del__”析构方法

-#### 1、基本概念&#xff08;构造函数与析构函数&#xff09; 特殊函数&#xff1a;由系统自动执行&#xff0c;在程序中不可显式地调用他们 构造函数&#xff1a; 建立对象时对对象的数据成员进行初始化&#xff08;对象初始化&#xff09; 析构函数&#xff1a; 对象生命期…...

支付系统核心架构设计思路(万能通用)

文章目录1. 支付系统总览核心系统交互业务图谱2. 核心系统解析交易核心交易核心基础交易类型抽象多表聚合 & 订单关联支付核心支付核心总览支付行为编排异常处理渠道网关资金核算3. 服务治理平台统一上下文数据一致性治理CAS校验幂等 & 异常补偿对账准实时对账DB拆分异…...

python实现mongdb的双活

如何用python实现mongdb的双活&#xff0c;两个数据库实时同步&#xff1f; 可以使用Pymongo库&#xff0c;它可以提供同步的API来实现MongoDB的双活&#xff0c;两个数据库实时同步。还可以使用MongoDB的复制集功能来进行实时同步。 Pymongo库提供什么同步的API来实现MongoD…...

LeetCode-110. 平衡二叉树

目录题目分析递归法题外话题目来源 110. 平衡二叉树 题目分析 平很二叉树:一个二叉树每个节点 的左右两个子树的高度差的绝对值不超过 1 。 二叉树节点的深度和二叉树节点的高度 递归法 递归三步曲 1.明确递归函数的参数和返回值 参数&#xff1a;当前传入节点。 返回值…...

Python蓝桥杯训练:基本数据结构 [链表]

Python蓝桥杯训练&#xff1a;基本数据结构 [链表] 文章目录Python蓝桥杯训练&#xff1a;基本数据结构 [链表]一、链表理论基础知识二、有关链表的一些常见操作三、力扣上面一些有关链表的题目练习1、[移除链表元素](https://leetcode.cn/problems/remove-linked-list-element…...

华为OD机试 - 找字符(Python)| 真题+思路+代码

找字符 题目 给定两个字符串, 从字符串2中找出字符串1中的所有字符, 去重并按照 ASCII 码值从小到大排列。 输入 字符范围满足 ASCII 编码要求, 输入字符串1长度不超过1024, 字符串2长度不超过100。 输出描述 按照 ASCII 由小到大排序 示例一 输入 bach bbaaccddf…...

接口测试中缓存处理策略

在接口测试中&#xff0c;缓存处理策略是一个关键环节&#xff0c;直接影响测试结果的准确性和可靠性。合理的缓存处理策略能够确保测试环境的一致性&#xff0c;避免因缓存数据导致的测试偏差。以下是接口测试中常见的缓存处理策略及其详细说明&#xff1a; 一、缓存处理的核…...

OpenLayers 可视化之热力图

注&#xff1a;当前使用的是 ol 5.3.0 版本&#xff0c;天地图使用的key请到天地图官网申请&#xff0c;并替换为自己的key 热力图&#xff08;Heatmap&#xff09;又叫热点图&#xff0c;是一种通过特殊高亮显示事物密度分布、变化趋势的数据可视化技术。采用颜色的深浅来显示…...

树莓派超全系列教程文档--(62)使用rpicam-app通过网络流式传输视频

使用rpicam-app通过网络流式传输视频 使用 rpicam-app 通过网络流式传输视频UDPTCPRTSPlibavGStreamerRTPlibcamerasrc GStreamer 元素 文章来源&#xff1a; http://raspberry.dns8844.cn/documentation 原文网址 使用 rpicam-app 通过网络流式传输视频 本节介绍来自 rpica…...

【解密LSTM、GRU如何解决传统RNN梯度消失问题】

解密LSTM与GRU&#xff1a;如何让RNN变得更聪明&#xff1f; 在深度学习的世界里&#xff0c;循环神经网络&#xff08;RNN&#xff09;以其卓越的序列数据处理能力广泛应用于自然语言处理、时间序列预测等领域。然而&#xff0c;传统RNN存在的一个严重问题——梯度消失&#…...

HBuilderX安装(uni-app和小程序开发)

下载HBuilderX 访问官方网站&#xff1a;https://www.dcloud.io/hbuilderx.html 根据您的操作系统选择合适版本&#xff1a; Windows版&#xff08;推荐下载标准版&#xff09; Windows系统安装步骤 运行安装程序&#xff1a; 双击下载的.exe安装文件 如果出现安全提示&…...

VTK如何让部分单位不可见

最近遇到一个需求&#xff0c;需要让一个vtkDataSet中的部分单元不可见&#xff0c;查阅了一些资料大概有以下几种方式 1.通过颜色映射表来进行&#xff0c;是最正规的做法 vtkNew<vtkLookupTable> lut; //值为0不显示&#xff0c;主要是最后一个参数&#xff0c;透明度…...

微信小程序云开发平台MySQL的连接方式

注&#xff1a;微信小程序云开发平台指的是腾讯云开发 先给结论&#xff1a;微信小程序云开发平台的MySQL&#xff0c;无法通过获取数据库连接信息的方式进行连接&#xff0c;连接只能通过云开发的SDK连接&#xff0c;具体要参考官方文档&#xff1a; 为什么&#xff1f; 因为…...

JDK 17 新特性

#JDK 17 新特性 /**************** 文本块 *****************/ python/scala中早就支持&#xff0c;不稀奇 String json “”" { “name”: “Java”, “version”: 17 } “”"; /**************** Switch 语句 -> 表达式 *****************/ 挺好的&#xff…...

【VLNs篇】07:NavRL—在动态环境中学习安全飞行

项目内容论文标题NavRL: 在动态环境中学习安全飞行 (NavRL: Learning Safe Flight in Dynamic Environments)核心问题解决无人机在包含静态和动态障碍物的复杂环境中进行安全、高效自主导航的挑战&#xff0c;克服传统方法和现有强化学习方法的局限性。核心算法基于近端策略优化…...

【Go语言基础【12】】指针:声明、取地址、解引用

文章目录 零、概述&#xff1a;指针 vs. 引用&#xff08;类比其他语言&#xff09;一、指针基础概念二、指针声明与初始化三、指针操作符1. &&#xff1a;取地址&#xff08;拿到内存地址&#xff09;2. *&#xff1a;解引用&#xff08;拿到值&#xff09; 四、空指针&am…...