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

【NC50937】货仓选址

题目

货仓选址

二分,前缀和,数学推导

思路

由题意可知货仓的位置是可以和商店的位置重合的。首先应该将商店的坐标从小到大排序,然后假设商店的坐标为 a i a_i ai,货仓的坐标为 x x x,货仓左侧第一家商店(可能和货仓重合)的坐标为 a k a_k ak,则由题意计算出的距离应该为:
d i s t = ∑ i = 0 k ( x − a i ) + ∑ i = k + 1 n − 1 ( a i − x ) = ( k + 1 ) x − ∑ i = 0 k a i + ∑ i = k + 1 n − 1 a i − ( n − 1 − k ) x dist=\sum_{i=0}^k(x-a_i)+\sum_{i=k+1}^{n-1}(a_i-x)=(k+1)x-\sum_{i=0}^ka_i+\sum_{i=k+1}^{n-1}a_i-(n-1-k)x dist=i=0k(xai)+i=k+1n1(aix)=(k+1)xi=0kai+i=k+1n1ai(n1k)x
根据上面的推导最直观的思路就是枚举从 a 0 → a i a_0\to a_i a0ai 的所有坐标,然后老老实实地计算每个 d i s t dist dist 取最小值,这种思路需要用到二分,具体见代码。

这里要记录的并不是像上面那样简单模拟的思路,而是更为巧妙一些的:

假设给出的商店坐标(排好序之后)为 1 , 2 , 6 , 9 1,2,6,9 1,2,6,9
则按上面模拟的思路计算可得:

货仓位置距离
114
212
312
412
512
612
714
816
918

为什么不枚举小于 a 0 a_0 a0 和大于 a n a_n an 的位置呢?这个问题留给读者。
由上面的表格可以得出,似乎越往商店的中部位置靠近,距离就越短
不妨直接研究中部的商店,这里的商店数是偶数个,则研究中间的两个商店,我们会得到一个有趣的结论:
在中部的两个商店之间建立货仓的话,各商店到货仓的距离是不变的,并且距离为两两对称的商店之间的距离之和,比如例子里面的距离就是 6 − 2 + 9 − 1 = 12 6-2+9-1=12 62+91=12
所以这题可以直接求两两对称商店的距离之差的和即可,奇数个商店数就将货仓建立在最中间的商店处即可。具体的证明这里不做记录,但是是很容易想通的。

代码

代码一:二分模拟

#include <limits.h>
#include <stdio.h>
#include <stdlib.h>
typedef long long LL;int cmp(const void* a, const void* b) { return *(int*)a - *(int*)b; }// 寻找第一个小于等于 target 的元素的下标,没有则返回 -1
int first_le(int* arr, int n, int target) {int l = 0, r = n - 1, mid = 0;while (l <= r) {mid = l + ((r - l) >> 1);if (arr[mid] <= target) {if (mid == n - 1 || arr[mid + 1] > target) {return mid;}l = mid + 1;} else {r = mid - 1;}}return -1;
}int main(void) {int n = 0;scanf("%d", &n);int a[n], i = 0;for (i = 0; i < n; i++) {scanf("%d", a + i);}qsort(a, n, sizeof(int), cmp);LL sum[n], ans = LLONG_MAX, t = 0;sum[0] = a[0];for (i = 1; i < n; i++) {sum[i] = sum[i - 1] + a[i];}for (LL x = a[0]; x <= a[n - 1]; x++) {i = first_le(a, n, x);t = (i + 1) * x - sum[i] + sum[n - 1] - sum[i] - (n - 1 - i) * x;if (t < ans) ans = t;}printf("%lld\n", ans);return 0;
}

代码二:数学推导

#include <stdio.h>
#include <stdlib.h>#define N 1000005typedef long long LL;int cmp(const void* a, const void* b) { return *(int*)a - *(int*)b; }int main(void) {int n = 0;scanf("%d", &n);int a[n], i = 0;LL ans = 0;for (i = 0; i < n; i++) {scanf("%d", a + i);}qsort(a, n, sizeof(int), cmp);for (i = n >> 1; i < n; i++) {ans += a[i] - a[n - i - 1];}printf("%lld\n", ans);return 0;
}

相关文章:

【NC50937】货仓选址

题目 货仓选址 二分&#xff0c;前缀和&#xff0c;数学推导 思路 由题意可知货仓的位置是可以和商店的位置重合的。首先应该将商店的坐标从小到大排序&#xff0c;然后假设商店的坐标为 a i a_i ai​&#xff0c;货仓的坐标为 x x x&#xff0c;货仓左侧第一家商店&#x…...

Nginx配置使用笔记

Nginx配置使用笔记 前言 官网下载压缩包https://nginx.org/ 解压完成后当前目录cmd输入nginx指令启动 访问http://localhost:80确认启动成功 1.部署前端项目 部署前端项目到路径E:\Workspaces\Vscode\app-web 2.0配置nginx.conf文件 在nginx安装的conf目录下新建一个文件夹l…...

GridLayoutManager 中的一些坑

前言 如果GridLayoutManager使用item的布局都是wrap_cotent 那么会在布局更改时会出现一些出人意料的情况。&#xff08;本文完全不具备可读性和说教性&#xff0c;仅为博主方便查找问题&#xff09; 布局item: <!--layout_item.xml--> <?xml version"1.0&qu…...

算法实验二 矩阵最小路径和 LIS

算法实验课二 矩阵最小路径和 leetcode裸题 最小路径和 给定一个包含非负整数的 *m* x *n* 网格 grid &#xff0c;请找出一条从左上角到右下角的路径&#xff0c;使得路径上的数字总和为最小。 说明&#xff1a;每次只能向下或者向右移动一步。 示例 1&#xff1a; 输入&…...

Apache Paimon实时数据糊介绍

Apache Paimon 是一种湖格式,可以使用 Flink 和 Spark 构建实时 数据糊 架构,用于流式和批处理操作。Paimon 创新地将湖格式和 LSM(日志结构合并树)结构相结合,将实时流式更新引入湖架构中。 Paimon 提供以下核心功能: 实时更新: 主键表支持大规模更新的写入,具有非常…...

计算机网络:数据链路层 - 可靠传输协议

计算机网络&#xff1a;数据链路层 - 可靠传输协议 可靠传输概念停止-等待协议 SW回退N帧协议 GBN选择重传协议 SR 可靠传输概念 如下所示&#xff0c;帧在传输过程中受到干扰&#xff0c;产生了误码。接收方的数据链路层&#xff0c;通过真伪中的真检验序列 FCS 字段的值&…...

苍穹外卖07(缓存菜品,SpringCache,缓存套餐,添加购物车菜品和套餐多下单,查看购物车,清除购物车,删除购物车中一个商品)

目录 一、缓存菜品 1 问题说明 2 实现思路 3 代码开发&#xff1a;修改DishServiceImpl 4 功能测试 二、SpringCache 1. 介绍 2. 使用语法 1 起步依赖 2 使用要求 3 常用注解 4 SpEL表达式(了解备用) 5 步骤小结 3.入门案例 1 准备环境 2 使用入门 1 引导类上加…...

C语言第三十八弹---编译和链接

✨个人主页&#xff1a; 熬夜学编程的小林 &#x1f497;系列专栏&#xff1a; 【C语言详解】 【数据结构详解】 编译和链接 1、翻译环境和运行环境 2、翻译环境 2.1、预处理&#xff08;预编译&#xff09; 2.2、编译 2.2.1、词法分析 2.2.2、语法分析 2.2.3、语义分…...

无人售货奶柜:开启便捷生活的新篇章

无人售货奶柜&#xff1a;开启便捷生活的新篇章 在这个快节奏的现代生活中&#xff0c;科技的革新不仅为我们带来了前所未有的便利&#xff0c;更在不经意间改变着我们的日常。其中&#xff0c;无人售货技术的出现&#xff0c;尤其是无人售货奶柜&#xff0c;已经成为我们生活…...

STM32为什么不能跑Linux?

STM32是一系列基于ARM Cortex-M微控制器的产品&#xff0c;它们主要用于嵌入式系统中。而Linux则是一个开源的类Unix操作系统&#xff0c;主要面向的是桌面电脑、服务器等资源丰富的计算机。虽然理论上可以将Linux移植到STM32上运行&#xff0c;但是由于两者之间存在着很多技术…...

Dubbo 3.x源码(18)—Dubbo服务引用源码(1)

基于Dubbo 3.1&#xff0c;详细介绍了Dubbo服务的发布与引用的源码。 此前我们学习了Dubbo的服务导出的源码&#xff0c;在DubboBootstrapApplicationListener#startSync方法中&#xff0c;在调用了exportServices方法进行服务导出之后&#xff0c;立即调用了referServices方法…...

设计模式:工厂模式和抽象工厂模式的区别

定义 工厂模式(Factory Pattern)通常指的是工厂方法模式(Factory Method Pattern),它定义了一个创建对象的方法,由子类决定要实例化的类。工厂方法让类的实例化推迟到子类。 抽象工厂模式(Abstract Factory Pattern)提供了一个接口,用于创建相关或依赖对象的家族,而…...

python面试题(36~50)

36、如何取一个整数的绝对值? 这可以通过abs函数来实现。 abs(2) #> 2 abs(-2) #> 2 37、如何将两个列表组合成一个元组列表? 可以使用zip函数将列表组合成一个元组列表。这不仅仅限于使用两个列表。也适合3个或更多列表的情况。 a [a,b,c] b [1,2,3] [(k,v) fo…...

Vue 样式技巧总结与整理[中级局]

SFC&#xff08;单文件组件&#xff09;由 3 个不同的实体组成&#xff1a;模板、脚本和样式。三者都很重要&#xff0c;但后者往往被忽视&#xff0c;即使它可能变得复杂&#xff0c;且经常导致挫折和 bug。 更好的理解可以改善代码审查并减少调试时间。 这里有 7 个奇技淫巧…...

cesium加载.tif格式文件

最近项目中有需要直接加载三方给的后缀名tif格式的文件 <script src"https://cdn.jsdelivr.net/npm/geotiff"></script> 或者 yarn add geotiff npm install geotiff 新建tifs.js import GeoTIFF, { fromBlob, fromUrl, fromArrayBuffer } from geotif…...

分布式全闪占比剧增 152%,2023 年企业存储市场报告发布

近日&#xff0c;IDC 发布了 2023 年度的中国存储市场报告。根据该报告&#xff0c;在 2023 年软件定义存储的市场占比进一步扩大&#xff0c;分布式全闪的增长尤其亮眼&#xff0c;其市场份额从 2022 年的 7% 剧增到 2023 年的 17.7%&#xff0c;增长了 152%。 01 中国企业存…...

LeetCode 707. 设计链表(单链表、(非循环)双链表 模板)

你可以选择使用单链表或者双链表&#xff0c;设计并实现自己的链表。 单链表中的节点应该具备两个属性&#xff1a;val 和 next 。val 是当前节点的值&#xff0c;next 是指向下一个节点的指针/引用。 如果是双向链表&#xff0c;则还需要属性 prev 以指示链表中的上一个节点…...

深入了解Flutter中Overlay的介绍以及使用

Flutter Overlay 介绍 在 Flutter 中&#xff0c;Overlay 是一种特殊的 Widget&#xff0c;它可以用来在应用程序的其他部分之上显示内容。Overlay 非常适合用于显示模态对话框、弹出菜单、工具提示等。 Overlay 的工作原理 Overlay 位于 Flutter 的渲染树之外&#xff0c;这…...

文本直接生成2分钟视频,即将开源模型StreamingT2V

Picsart人工智能研究所、德克萨斯大学和SHI实验室的研究人员联合推出了StreamingT2V视频模型。通过文本就能直接生成2分钟、1分钟等不同时间&#xff0c;动作一致、连贯、没有卡顿的高质量视频。 虽然StreamingT2V在视频质量、多元化等还无法与Sora媲美&#xff0c;但在高速运…...

时序预测 | Matlab实现SOM-BP自组织映射结合BP神经网络时间序列预测

时序预测 | Matlab实现SOM-BP自组织映射结合BP神经网络时间序列预测 目录 时序预测 | Matlab实现SOM-BP自组织映射结合BP神经网络时间序列预测预测效果基本介绍程序设计参考资料 预测效果 基本介绍 1.Matlab实现SOM-BP自组织映射结合BP神经网络时间序列预测&#xff08;完整源码…...

FPGA高端图像处理开发板-->鲲叔4EV:12G-SDI、4K HDMI2.0、MIPI等接口谁敢与我争锋?

目录 前言鲲叔4EV----高端FPGA图像处理开发板核心板描述底板描述配套例程源码描述配套服务描述开发板测试视频演示开发板获取 前言 在CSDN写博客传播FPGA开发经验已经一年多了&#xff0c;帮助了不少人&#xff0c;也得罪了不少人&#xff0c;有的人用我的代码赢得了某些比赛、…...

linux练习-交互式传参

在shell脚本中&#xff0c;read 向用户显示一行文本并接受用户输入 #!/bin/bash read -p 依次输入你的姓名、年龄、家乡 name age home echo 我是$name,年龄$age,我来自$home...

【数据结构(一)】初识数据结构

❣博主主页: 33的博客❣ ▶文章专栏分类: Java从入门到精通◀ &#x1f69a;我的代码仓库: 33的代码仓库&#x1f69a; &#x1faf5;&#x1faf5;&#x1faf5;关注我带你学更多数据结构知识 目录 1.前言2.集合架构3.时间和空间复杂度3.1算法效率3.2时间复杂度3.2.1大O的渐进…...

前端三剑客 —— CSS (第六节)

目录 内容回顾&#xff1a; 弹性布局属性介绍 案例演示 商品案例 布局分析 登录案例 网格布局 内容回顾&#xff1a; 变量&#xff1a;定义变量使用 --名称&#xff1a;值&#xff1b; 使用变量&#xff1a; 属性名&#xff1a;var&#xff08;--名称&#xff09;&a…...

MyBatis 解决上篇的参数绑定问题以及XML方式交互

前言 上文:MyBatis 初识简单操作-CSDN博客 上篇文章我们谈到的Spring中如何使用注解对Mysql进行交互 但是我们发现我们返回出来的数据明显有问题 我们发现后面三个字段的信息明显没有展示出来 下面我们来谈谈解决方案 解决方案 这里的原因本质上是因为mysql中和对象中的字段属性…...

Rust语言之属性宏(Attribute Macro)derive

文章目录 Rust语言之属性宏&#xff08;Attribute Macro&#xff09;derive Rust语言之属性宏&#xff08;Attribute Macro&#xff09;derive 属性宏是一种基于属性的宏&#xff0c;用于修改、扩展或注解 Rust 代码。它们通常用于为函数、结构体、枚举、模块等添加元数据或自…...

[技术闲聊]我对电路设计的理解(六)-原理图封装

电路设计的直观体现就是完整的原理图&#xff0c;绘制电路图阶段的第一步&#xff0c;绘制原理图封装库。 封装库一共有两种&#xff0c;一种是原理图封装库&#xff0c;一种是PCB封装库&#xff0c;如下图所示。 原理图封装和PCB封装之间的唯一关联就是 引脚位号&#xff0c;…...

算法(滑动窗口四)

1.串联所有单词的子串 给定一个字符串 s 和一个字符串数组 words。 words 中所有字符串 长度相同。 s 中的 串联子串 是指一个包含 words 中所有字符串以任意顺序排列连接起来的子串。 例如&#xff0c;如果 words ["ab","cd","ef"]&#xff…...

学习记录:bazel和cmake运行终端指令

Bazel和CMake都是用于构建软件项目的工具&#xff0c;但它们之间有一些重要的区别和特点&#xff1a; Bazel&#xff1a; Bazel是由Google开发的构建和测试工具&#xff0c;用于构建大规模的软件项目。它采用一种称为“基于规则”的构建系统&#xff0c;它利用构建规则和依赖关…...

蓝桥杯刷题--python-37-分解质因数

3491. 完全平方数 - AcWing题库 nint(input()) res1 i2 while i*i<n: if n%i0: t0 while n%i0: n//i t1 if t%2: res*i i1 if n>1: res*n print(res) 4658. 质因数个数 - AcWing题库…...

杭州高瑞网站建设/seo优化裤子关键词

为什么80%的码农都做不了架构师&#xff1f;>>> 按照NetBeans6.5最快安装方法安装NetBeas6.5成功后&#xff0c;NetBeans使用操作系统默认的语言&#xff0c;如果是中文版的操作系统&#xff0c;则使用中文版。如果你想使用英文版的NetBeans&#xff0c;在它本身的…...

南昌网站建设方案/网站 软件

论文地址&#xff1a;https://www.rose-hulman.edu/class/se/csse461/handouts/Day37/nister_d_146.pdf 摘要 我们展示了一个系统可以评估运动的一个立体头或者一个移动相机基于视频输入。这个系统运行在实时低时延以及运动评估使用航行目的。前端系统是一个特征跟踪器。点特征…...

本地网站环境搭建/怎么在网上推销产品

文章目录GitHub官网官网Demo指引zuul概念zuul功能授权和安全认证监控统计动态路由压测Load shadding [降低负载]Static Response handling [静态响应处理]Multiregion Resiliency1.zuul是一个提供动态路由&#xff0c;监控&#xff0c;弹性&#xff0c;安全等网关服务;GitHub官…...

wordpress文章页幻灯片/国产长尾关键词拘挖掘

机器人视觉系统是指用计算机来实现人的视觉功能&#xff0c;也就是用计算机来实现对客观的三维世界的识别。人类接收的信息70%以上来自视觉&#xff0c;人类视觉为人类提供了关于周围环境 最详细可靠的信息。人类视觉所具有的强大功能和完美的信息处理方式引起了智能研究者的极…...

网站建设/seo技术306

原文&#xff1a;http://www.asp.net/mvc/tutorials/getting-started-with-ef-using-mvc/creating-an-entity-framework-data-model-for-an-asp-net-mvc-application 【序】 Contoso大学示例程序为您演示了如何使用EntityFramework技术来创建一个完整的ASP.NET MVC程序&#xf…...

wordpress chinese-username插件/广东疫情最新情况

JavaScript基本包装类型&#xff0c;数据类型的方法 学习要点&#xff1a; 1.基本包装类型概述 2.Boolean类型 3.Number类型 4.String类型 为了便于操作基本类型值&#xff0c;ECMAScript提供了3个特殊的引用类型&#xff1a;Boolean、Number和String。这些类型与其他引用类型相…...