绝对值不等式运用(C++)

 货仓选址

 

 用数学公式表达题意,假设有位置a1~an,假设选址在x位置处,则有:min\left | a_1-x\right |+\left | a_2-x\right |+...+\left | a_n-x\right |

如何让这个最小,我们把两个式子整合一下,利用绝对值不等式:

(\left | a_1-x\right |+\left | a_n-x\right |)+(\left | a_2-x\right |+\left | a_{n-1}-x\right |)...\geqslant \left | a_n-a_1 \right |+ \left | a_{n-1}-a_2 \right |+...

 我们知道:

如下图所示:到A,B两点,利用反证法可知:只有在A,B之间的点到A,B距离最短(即下图黄色框选区域)

如果点多一些,我们扩展以下:

 

会发现:

奇数个时候,取中位数刚合适(取紫色区域中间);偶数取到中间两个数直接就可以。

根据数学表达式,我们发现的确满足取等条件,则说明正确。

核心代码:

res += abs(q[i] - q[n / 2])

为啥能直接写:因为不论奇数偶数,取到q[n/2]即可,编译器会自动取整。

#include <iostream>
#include <algorithm>
using namespace std;
const int N = 100010;
int n;
int a[N];
int main()
{
    scanf("%d", &n);
    for (int i = 0; i < n; i ++ ) scanf("%d", &a[i]);
    sort(a, a + n);
    int res = 0;
    for (int i = 0; i < n; i ++ ) res += abs(a[i] - a[n / 2]);
    printf("%d\n", res);
    return 0;
}

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:/a/791390.html

如若内容造成侵权/违法违规/事实不符,请联系我们进行投诉反馈qq邮箱809451989@qq.com,一经查实,立即删除!

相关文章

【深度学习入门篇 ②】Pytorch完成线性回归!

&#x1f34a;嗨&#xff0c;大家好&#xff0c;我是小森( &#xfe61;ˆoˆ&#xfe61; )&#xff01; 易编橙终身成长社群创始团队嘉宾&#xff0c;橙似锦计划领衔成员、阿里云专家博主、腾讯云内容共创官、CSDN人工智能领域优质创作者 。 易编橙&#xff1a;一个帮助编程小…

简单状压dp(以力扣464为例)

目录 1.状态压缩dp是啥&#xff1f; 2.题目分析 3.解题思路 4.算法分析 5.代码分析 6.代码一览 7.结语 1.状态压缩dp是啥&#xff1f; 顾名思义&#xff0c;状态压缩dp就是将原本会超出内存限制的存储改用更加有效的存储方式。简而言之&#xff0c;就是压缩dp的空间。 …

昇思MindSpore学习笔记6-05计算机视觉--SSD目标检测

摘要&#xff1a; 记录MindSpore AI框架使用SSD目标检测算法对图像内容识别的过程、步骤和方法。包括环境准备、下载数据集、数据采样、数据集加载和预处理、构建模型、损失函数、模型训练、模型评估等。 一、概念 1.模型简介 SSD目标检测算法 Single Shot MultiBox Detecto…

WebRTC群发消息API接口选型指南!怎么用?

WebRTC群发消息API接口安全性如何&#xff1f;API接口怎么优化&#xff1f; WebRTC技术在现代实时通信中占据了重要地位。对于需要实现群发消息功能的应用程序来说&#xff0c;选择合适的WebRTC群发消息API接口是至关重要的。AokSend将详细介绍WebRTC群发消息API接口的选型指南…

大数据开发者如何快速熟悉新公司业务

作为一名大数据开发工程师,进入一家新公司后快速熟悉业务是至关重要的。 目录 1. 了解产品形态故事1:电商平台的数据分析故事2:金融科技的风控系统故事3:社交媒体的推荐算法 2. 了解业务流程故事1:物流配送系统的优化故事2:医疗保险的理赔流程故事3:银行的贷款审批流程 3. 走…

openfoam生成的非均匀固体Solid数据分析、VTK数据格式分析、以及paraview官方用户指导文档和使用方法

一、openfoam生成的非均匀固体Solid数据分析 对于Solid/dealii-output文件&#xff0c;固体的数据文件&#xff0c; # vtk DataFile Version 3.0 #This file was generated by the deal.II library on 2024/7/10 at 9:46:15 ASCII DATASET UNSTRUCTURED_GRIDPOINTS 108000 do…

【算法】【二分法】二分法详解

先给y总打一个广告。&#xff08;我这种废物收不到钱&#xff09; 本科时候就在打蓝桥杯玩玩算法&#xff0c;当时听朋友的一个刷题且涵盖教程的网站&#xff0c;ACWING。 www.acwing.com 里面好处是大部分基础算法都有&#xff0c;Y总的视频&#xff01; y总我的神&#xff01…

IDEA之Debug的使用

自定义功能图表 功能说明 光标回到Debug行 执行到光标所在行 Force Step into Trace Current Stream Chain Reset Frame 重置方法入栈

C++基础学习笔记

1.命名空间(namespace) 1.什么是命名空间&命名空间的作用 1.在C/C中&#xff0c;变量、函数、类都是大量存在的&#xff0c;这些变量等的名称将都存在于全局作用域中&#xff0c;就会导致很多的命名冲突等。使用命名空间的目的就是对标识符的名称进行本地化&#xff0c;以…

Nginx七层(应用层)反向代理:UWSGI代理uwsgi_pass篇

Nginx七层&#xff08;应用层&#xff09;反向代理 UWSGI代理uwsgi_pass篇 - 文章信息 - Author: 李俊才 (jcLee95) Visit me at CSDN: https://jclee95.blog.csdn.netMy WebSite&#xff1a;http://thispage.tech/Email: 291148484163.com. Shenzhen ChinaAddress of this a…

JavaSE学习笔记第二弹——对象和多态(下)

今天我们继续复习与JavaSE相关的知识&#xff0c;使用的编译器仍然是IDEA2022&#xff0c;大家伙使用eclipse或其他编译环境是一样的&#xff0c;都可以。 目录 数组 定义 一维数组 ​编辑 二维数组 多维数组 数组的遍历 for循环遍历 ​编辑 foreach遍历 封装、继承和…

网络编程的学习之udp

Udp编程过程 Sento不会阻塞 实现聊天室效果 上线 聊天 下线 服务端需要一个地址&#xff0c;去保留名字和ip地址 交互的时候发结构体 下面这个宏只能在c语言里使用 ser.sin_port htons(50000); 上面是端口号50000以上&#xff0c;两边要一样 这里是不要让udp发的太快&am…

Git命令常规操作

目录 常用操作示意图 文件的状态变化周期 1. 创建文件 2. 修改原有文件 3. 删除原有文件 没有添加到暂存区的数据直接 rm 删除即可&#xff1a; 对于添加到暂存区的数据 文件或目录&#xff1a; 4. 重命名暂存区数据 5. 查看历史记录 6. 还原历史数据 恢复过程的原…

C/C++ list模拟

模拟准备 避免和库冲突&#xff0c;自己定义一个命名空间 namespace yx {template<class T>struct ListNode{ListNode<T>* _next;ListNode<T>* _prev;T _data;};template<class T>class list{typedef ListNode<T> Node;public:private:Node* _…

低代码平台赋能企业全面数字化转型

引言&#xff1a;在当今这个日新月异的数字化时代&#xff0c;企业正面临着前所未有的机遇与挑战。为了保持竞争力并实现可持续发展&#xff0c;企业亟需进行全面的数字化转型。而低代码平台作为数字化转型的重要工具&#xff0c;正以其独特的优势赋能企业&#xff0c;推动其向…

Ollama完整教程:本地LLM管理、WebUI对话、Python/Java客户端API应用

老牛同学在前面有关大模型应用的文章中&#xff0c;多次使用了Ollama来管理和部署本地大模型&#xff08;包括&#xff1a;Qwen2、Llama3、Phi3、Gemma2等&#xff09;&#xff0c;但对Ollama这个非常方便管理本地大模型的软件的介绍却很少。 目前&#xff0c;清华和智谱 AI 联…

[计网初识1] TCP/UDP

学习内容 1.TCP建立链接的3次握手&#xff0c;断开连接的4次挥手 2.TCP报文段组成 内容 1.TCP 建立连接的3次握手? 假设主动方是客户端&#xff0c;被动方是服务端。 第一次 客户端给服务端发送 “hello,我是客户端” (TCP段中 SYN1) 第二次 服务端给客户端发送"我接…

汽车免拆诊断案例 | 2016款保时捷Macan车发动机故障灯异常点亮

故障现象  一辆2016款保时捷Macan车&#xff0c;搭载CYP发动机&#xff0c;累计行驶里程约为11.2万km。车主进厂反映&#xff0c;发动机故障灯异常点亮。 故障诊断  接车后试车&#xff0c;发动机怠速无明显异常&#xff0c;组合仪表上的发动机故障灯异常点亮。用故障检测仪…

AI in Finance 金融领域AI应用-基于DeepNLP AI App Store 真实用户评论打分和排名

AI在金融领域应用 AI in Finance 金融服务领域的AI应用和传统的金融智能应用不同。传统金融智能应用包括如风险评估 (Risk assessment), 风险管理&#xff08;Risk management), 欺诈检测 (Fraud Detection&#xff09;等等。 通用AI大模型和人工智能应用如ChatGPT&#xff0c…

echart5.5.1版本,倒三角柱状图

加载方法 initChart1(title, id, tag) {var myChart echarts5.init(this.$refs[id]);const _this this;var option {title:{text: title||"",show: title?true:false,top: 24,left: 24},grid:{left: 54,top: 74,bottom: 44,right: 30,},xAxis: {type: category,d…