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

货仓选址 AcWing(JAVA)

在一条数轴上有 N家商店,它们的坐标分别为 A1∼AN。

现在需要在数轴上建立一家货仓,每天清晨,从货仓到每家商店都要运送商品。

为了提高效率,求把货仓建在何处,可以使得货仓到每家商店的距离之和最小。

输入格式:

第一行输入整数 N。

第二行 N个整数 A1∼AN。

输出格式:

输出一个整数,表示距离之和的最小值。

数据范围

1≤N≤100000,
0≤Ai≤40000

输入样例:

4
6 2 9 1

输出样例:

12

解题思路: 首先对于 a , b (a < b)取一个x数到a,b的距离之和最短,这个距离 dis = | x - a | + |x - b |。
而 | x - a | + |x - b | >= | b - a |。
即 当 x 在,a,b 之间的时候距离之和最短为 b - a。
在这里插入图片描述

而当 x 取 a,b 左右两边时,距离为 a - x + b - x = a + b - 2x 或者 x - a + x - b = 2x - a - b
在这里插入图片描述
显然后者是没有前者大的,所以对于任意两个数 a,b(a < b)时要想使得到a b的距离之和最短,那么x的位置得取a,b之间(包括 a,b两点)。

而对于a ,b ,c ,d,(a < b < c < d)要想使 x 到他们之间的距离之和最短,首先对于a,d 两点 x 应在a,d之间,在到a,d距离最短的基础上还要使到b,c的距离也最短,由于b,c本身就在a,d之间所以满足前一个条件,所以x在b,c之间取即可(包括b,c点),即取b 或 c 都可。

不管数组有多长以此类推即可。
所以找数组中位数的位置即可。先对数组排序,对偶数组 , 找中间任意两个数即可,对于奇数组找中间一个数即可,不管奇偶用 n / 2 表示中位数位置完全没有问题。

理论成立代码如下:

import java.util.*;public class Main {public static void main(String[] args) {Scanner sc = new Scanner(System.in);int n = sc.nextInt();int v[] = new int[n];for(int i = 0; i <n; i ++) v[i] = sc.nextInt();Arrays.sort(v);int sum = 0;for(int i = 0; i < n; i ++) sum = sum + Math.abs(v[i] - v[n / 2]);System.out.print(sum);}}

方法二(把 n / 2 变成 i / 2):

import java.util.*;public class Main {public static void main(String[] args) {Scanner sc = new Scanner(System.in);int n = sc.nextInt();int v[] = new int[n];for(int i = 0; i <n; i ++) v[i] = sc.nextInt();Arrays.sort(v);int sum = 0;for(int i = 0; i < n; i ++) sum = sum + Math.abs(v[i] - v[i / 2]);System.out.print(sum);}}

相关文章:

货仓选址 AcWing(JAVA)

在一条数轴上有 N家商店&#xff0c;它们的坐标分别为 A1∼AN。 现在需要在数轴上建立一家货仓&#xff0c;每天清晨&#xff0c;从货仓到每家商店都要运送商品。 为了提高效率&#xff0c;求把货仓建在何处&#xff0c;可以使得货仓到每家商店的距离之和最小。 输入格式&#…...

SPI+DMA传输性能比较

本文章仅仅简单记录32单片机的SPIDMA驱动显示屏的性能测试&#xff0c;这里不花费时间介绍SPI和DMA。 硬件材料&#xff1a;SPI显示屏一个&#xff0c;32单片机 软件材料&#xff1a; 1.LCD的SPI驱动显示程序&#xff08;SPI / SPIDMA&#xff09;&#xff1a; &#xff08;1&a…...

Centos7系统编译Hadoop3.3.4

1、背景 最近在学习hadoop&#xff0c;此篇文章简单记录一下通过源码来编译hadoop。为什么要重新编译hadoop源码&#xff0c;是因为为了匹配不同操作系统的本地库环境。 2、编译源码 2.1 下载并解压源码 [roothadoop01 ~]# mkdir /opt/hadoop [roothadoop01 ~]# cd /opt/had…...

pb并发控制

并发控制(一) 并发能力是指多用户在同一时间对相同数据同时访问的能力。一般的关系型数据库都具 有并发控制的能力,但是这种并发功能也会对数据的一致性带来危险。试想若有两个用 户都试图访问某个银行用户的记录并同时要求修改该用户的存款余额时,情况将会怎样 呢?我们可以…...

登录拦截器

文章目录前言一、interceptor1.interceptor 包下新建loginInterceptor.java2.config 包下新建 AdminWebConfig.java3.返回登录页面接收提示信息前言 本篇主要介绍spring框架里提供的 HandlerInterceptor 拦截器做登录拦截。 一、interceptor 1.interceptor 包下新建loginInte…...

STM32 - HAL库UART串口

1.串口初始化配置/******************************************************************************* Function: BSP_UART_Init Description: 串口初始化 Input: instance 串口号baudRate: 波特率 Output: 无 Return: 无 ************************************************…...

Vue3 的状态管理库(Pinia)

目录前言&#xff1a;一、什么是 Pinai二、安装与使用pinia三、什么是 store四、state1. 定义 state2. 组件中访问 state五、Getters1. 定义 Getters2. 在组件中使用 Getters六、Actions1. 定义Actions2. 组件中访问 Actions总结&#xff1a;前言&#xff1a; 在编写vue里的项目…...

信息系统项目管理师知识点汇总(2023最新)

信息系统项目管理师 信息系统项目管理师简介如何应对考试考试细节与学习 十大管理 十大管理四十七过程 信息化和信息系统 项目管理基础 项目整体管理 项目范围管理 项目进度管理 项目成本管理 项目质量管理 项目人力资源管理 项目沟通管理 项目干系人管理 项目风险…...

标题标题标题

图床&#xff08;Typora uPic/PicGo 七牛云&#xff09; 图床&#xff08;Typora uPic/PicGo 七牛云&#xff09; 笔者平时使用 Typora 编写 markdown 文档&#xff0c;文档中常常会放置图片&#xff0c;如果文档不需要分享的话&#xff0c;其实讲图片存放在本地就可以了…...

OKR学习总结二

总结 绩效管理不是进行事后管理&#xff0c;而是参与整个过程并进行实时把控。 我们将受益目标分为两个子目标&#xff1a; 新增收入和重复收入。第一部分目标由市场营销部承担&#xff0c;第二个目标则由产品部承担。 简而言之&#xff0c;文化是一系列价值观和信仰的体现&…...

MAC中docker搭建fastdfs

1:首先搭建Docker2:通过Docker搭建fastdfs&#xff08;1&#xff09;查找镜像打开终端通命令查找fastdfs的镜像docker search fastdfs&#xff08;二&#xff09;拉取镜像在找到合适的镜像后执行命令:docker pull delron/fastdfs&#xff08;三&#xff09; 创建storage和track…...

JavaScript 变量

变量是用于存储信息的"容器"。实例var x5;var y6;var zxy;尝试一下 就像代数那样x5y6zxy在代数中&#xff0c;我们使用字母&#xff08;比如 x&#xff09;来保存值&#xff08;比如 5&#xff09;。通过上面的表达式 zxy&#xff0c;我们能够计算出 z 的值为 11。在…...

【前端验证】环境仿真中对于寄存器配置的随机策略讨论

前言 本篇文章旨在讨论环境仿真中对于寄存器配置的随机。 寄存器域的随机性 使用ralgen生成的寄存器本身是rand属性的,也就是说其自身是可以通过约束随机的方式在用例中进行随机性配置的,比如下面这个寄存器: class ral_reg_REG_PRJ_sys_cfg_base_config extends uvm_re…...

Servlet如何读取Web资源文件?【操作演示】

在实际开发中&#xff0c;有时候可能会需要读取Web应用中的一些资源文件&#xff0c;比如配置文件&#xff0c;图片等。为此&#xff0c;在ServletContext接口中定义了一些读取Web资源的方法&#xff0c;这些方法是依靠Servlet容器来实现的。Servlet容器根据资源文件相对于Web应…...

[ vulhub漏洞复现篇 ] Drupal 远程代码执行漏洞(CVE-2019-6339)

&#x1f36c; 博主介绍 &#x1f468;‍&#x1f393; 博主介绍&#xff1a;大家好&#xff0c;我是 _PowerShell &#xff0c;很高兴认识大家~ ✨主攻领域&#xff1a;【渗透领域】【数据通信】 【通讯安全】 【web安全】【面试分析】 &#x1f389;点赞➕评论➕收藏 养成习…...

flex-shrink和felx-grow

本文就是简单的介绍下flex-shrink和felx-grow的作用和计算方式吧&#xff1b;关于这个介绍也是很多&#xff1b;flex-shrinkflex-shrink是flex布局中的一种方式&#xff0c;简单来说&#xff0c;就是当布局大小小于容器大小的时候&#xff0c;使用flex-shrink能够按照一定的比例…...

将HTTP接口配置成HTTPS

一、使用Java的keytool.exe程序生成本机的TLS许可找到Java的jdk目录进入bin默认安装路径C:\Program Files\Java\jdk1.8.0_91\bin 进入命令面板&#xff0c;在bin的路径栏中输入cmd敲击回车即可使用keytoolkeytool -genkeypair -alias tomcat_https -keypass 123456 -keyalg RSA…...

YOLOV5报错解决办法

&#x1f308;&#x1f308;&#x1f604;&#x1f604; 欢迎来到茶色岛独家岛屿&#xff0c;本期将为大家揭晓YOLOV5报错解决办法&#xff0c;做好准备了么&#xff0c;那么开始吧。 &#x1f332;&#x1f332;&#x1f434;&#x1f434; 1.在pycharm终端使用pip install…...

java final关键字 详解

概述&#xff1a;作用&#xff1a;细节&#xff1a;演示&#xff1a;总结&#xff1a;一、概述 : final [ˈ faɪnl]&#xff0c;最终的&#xff0c;最后的&#xff0c;决定性的&#xff0c;不可改变的。final作为Java中的一个关键字可以用来修饰类&#xff0c;方法&#xff0c…...

Vbs_To_Exe制作简易exe程序

文章目录一、准备vbs脚本文件二、工具打包exe一、准备vbs脚本文件 新建一个文本文档 复制下面代码到文本文档中 Set speech CreateObject("SAPI.SpVoice") speech.Speak "l love you!"修改文本后缀为.vbs。编码选择ANSI&#xff08;解决中文乱码问题&am…...

SpringBoot-17-MyBatis动态SQL标签之常用标签

文章目录 1 代码1.1 实体User.java1.2 接口UserMapper.java1.3 映射UserMapper.xml1.3.1 标签if1.3.2 标签if和where1.3.3 标签choose和when和otherwise1.4 UserController.java2 常用动态SQL标签2.1 标签set2.1.1 UserMapper.java2.1.2 UserMapper.xml2.1.3 UserController.ja…...

Swift 协议扩展精进之路:解决 CoreData 托管实体子类的类型不匹配问题(下)

概述 在 Swift 开发语言中&#xff0c;各位秃头小码农们可以充分利用语法本身所带来的便利去劈荆斩棘。我们还可以恣意利用泛型、协议关联类型和协议扩展来进一步简化和优化我们复杂的代码需求。 不过&#xff0c;在涉及到多个子类派生于基类进行多态模拟的场景下&#xff0c;…...

测试markdown--肇兴

day1&#xff1a; 1、去程&#xff1a;7:04 --11:32高铁 高铁右转上售票大厅2楼&#xff0c;穿过候车厅下一楼&#xff0c;上大巴车 &#xffe5;10/人 **2、到达&#xff1a;**12点多到达寨子&#xff0c;买门票&#xff0c;美团/抖音&#xff1a;&#xffe5;78人 3、中饭&a…...

学习STC51单片机31(芯片为STC89C52RCRC)OLED显示屏1

每日一言 生活的美好&#xff0c;总是藏在那些你咬牙坚持的日子里。 硬件&#xff1a;OLED 以后要用到OLED的时候找到这个文件 OLED的设备地址 SSD1306"SSD" 是品牌缩写&#xff0c;"1306" 是产品编号。 驱动 OLED 屏幕的 IIC 总线数据传输格式 示意图 …...

vue3+vite项目中使用.env文件环境变量方法

vue3vite项目中使用.env文件环境变量方法 .env文件作用命名规则常用的配置项示例使用方法注意事项在vite.config.js文件中读取环境变量方法 .env文件作用 .env 文件用于定义环境变量&#xff0c;这些变量可以在项目中通过 import.meta.env 进行访问。Vite 会自动加载这些环境变…...

全志A40i android7.1 调试信息打印串口由uart0改为uart3

一&#xff0c;概述 1. 目的 将调试信息打印串口由uart0改为uart3。 2. 版本信息 Uboot版本&#xff1a;2014.07&#xff1b; Kernel版本&#xff1a;Linux-3.10&#xff1b; 二&#xff0c;Uboot 1. sys_config.fex改动 使能uart3(TX:PH00 RX:PH01)&#xff0c;并让boo…...

JVM暂停(Stop-The-World,STW)的原因分类及对应排查方案

JVM暂停(Stop-The-World,STW)的完整原因分类及对应排查方案,结合JVM运行机制和常见故障场景整理而成: 一、GC相关暂停​​ 1. ​​安全点(Safepoint)阻塞​​ ​​现象​​:JVM暂停但无GC日志,日志显示No GCs detected。​​原因​​:JVM等待所有线程进入安全点(如…...

在web-view 加载的本地及远程HTML中调用uniapp的API及网页和vue页面是如何通讯的?

uni-app 中 Web-view 与 Vue 页面的通讯机制详解 一、Web-view 简介 Web-view 是 uni-app 提供的一个重要组件&#xff0c;用于在原生应用中加载 HTML 页面&#xff1a; 支持加载本地 HTML 文件支持加载远程 HTML 页面实现 Web 与原生的双向通讯可用于嵌入第三方网页或 H5 应…...

Mobile ALOHA全身模仿学习

一、题目 Mobile ALOHA&#xff1a;通过低成本全身远程操作学习双手移动操作 传统模仿学习&#xff08;Imitation Learning&#xff09;缺点&#xff1a;聚焦与桌面操作&#xff0c;缺乏通用任务所需的移动性和灵活性 本论文优点&#xff1a;&#xff08;1&#xff09;在ALOHA…...

Python 包管理器 uv 介绍

Python 包管理器 uv 全面介绍 uv 是由 Astral&#xff08;热门工具 Ruff 的开发者&#xff09;推出的下一代高性能 Python 包管理器和构建工具&#xff0c;用 Rust 编写。它旨在解决传统工具&#xff08;如 pip、virtualenv、pip-tools&#xff09;的性能瓶颈&#xff0c;同时…...