当前位置: 首页 > 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…...

label-studio的使用教程(导入本地路径)

文章目录 1. 准备环境2. 脚本启动2.1 Windows2.2 Linux 3. 安装label-studio机器学习后端3.1 pip安装(推荐)3.2 GitHub仓库安装 4. 后端配置4.1 yolo环境4.2 引入后端模型4.3 修改脚本4.4 启动后端 5. 标注工程5.1 创建工程5.2 配置图片路径5.3 配置工程类型标签5.4 配置模型5.…...

React Native 导航系统实战(React Navigation)

导航系统实战&#xff08;React Navigation&#xff09; React Navigation 是 React Native 应用中最常用的导航库之一&#xff0c;它提供了多种导航模式&#xff0c;如堆栈导航&#xff08;Stack Navigator&#xff09;、标签导航&#xff08;Tab Navigator&#xff09;和抽屉…...

循环冗余码校验CRC码 算法步骤+详细实例计算

通信过程&#xff1a;&#xff08;白话解释&#xff09; 我们将原始待发送的消息称为 M M M&#xff0c;依据发送接收消息双方约定的生成多项式 G ( x ) G(x) G(x)&#xff08;意思就是 G &#xff08; x ) G&#xff08;x) G&#xff08;x) 是已知的&#xff09;&#xff0…...

什么是库存周转?如何用进销存系统提高库存周转率?

你可能听说过这样一句话&#xff1a; “利润不是赚出来的&#xff0c;是管出来的。” 尤其是在制造业、批发零售、电商这类“货堆成山”的行业&#xff0c;很多企业看着销售不错&#xff0c;账上却没钱、利润也不见了&#xff0c;一翻库存才发现&#xff1a; 一堆卖不动的旧货…...

FFmpeg:Windows系统小白安装及其使用

一、安装 1.访问官网 Download FFmpeg 2.点击版本目录 3.选择版本点击安装 注意这里选择的是【release buids】&#xff0c;注意左上角标题 例如我安装在目录 F:\FFmpeg 4.解压 5.添加环境变量 把你解压后的bin目录&#xff08;即exe所在文件夹&#xff09;加入系统变量…...

Proxmox Mail Gateway安装指南:从零开始配置高效邮件过滤系统

&#x1f49d;&#x1f49d;&#x1f49d;欢迎莅临我的博客&#xff0c;很高兴能够在这里和您见面&#xff01;希望您在这里可以感受到一份轻松愉快的氛围&#xff0c;不仅可以获得有趣的内容和知识&#xff0c;也可以畅所欲言、分享您的想法和见解。 推荐&#xff1a;「storms…...

Ubuntu系统多网卡多相机IP设置方法

目录 1、硬件情况 2、如何设置网卡和相机IP 2.1 万兆网卡连接交换机&#xff0c;交换机再连相机 2.1.1 网卡设置 2.1.2 相机设置 2.3 万兆网卡直连相机 1、硬件情况 2个网卡n个相机 电脑系统信息&#xff0c;系统版本&#xff1a;Ubuntu22.04.5 LTS&#xff1b;内核版本…...

C++_哈希表

本篇文章是对C学习的哈希表部分的学习分享 相信一定会对你有所帮助~ 那咱们废话不多说&#xff0c;直接开始吧&#xff01; 一、基础概念 1. 哈希核心思想&#xff1a; 哈希函数的作用&#xff1a;通过此函数建立一个Key与存储位置之间的映射关系。理想目标&#xff1a;实现…...

规则与人性的天平——由高考迟到事件引发的思考

当那位身着校服的考生在考场关闭1分钟后狂奔而至&#xff0c;他涨红的脸上写满绝望。铁门内秒针划过的弧度&#xff0c;成为改变人生的残酷抛物线。家长声嘶力竭的哀求与考务人员机械的"这是规定"&#xff0c;构成当代中国教育最尖锐的隐喻。 一、刚性规则的必要性 …...

用神经网络读懂你的“心情”:揭秘情绪识别系统背后的AI魔法

用神经网络读懂你的“心情”:揭秘情绪识别系统背后的AI魔法 大家好,我是Echo_Wish。最近刷短视频、看直播,有没有发现,越来越多的应用都开始“懂你”了——它们能感知你的情绪,推荐更合适的内容,甚至帮客服识别用户情绪,提升服务体验。这背后,神经网络在悄悄发力,撑起…...