当前位置: 首页 > 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;完整源码…...

MPNet:旋转机械轻量化故障诊断模型详解python代码复现

目录 一、问题背景与挑战 二、MPNet核心架构 2.1 多分支特征融合模块(MBFM) 2.2 残差注意力金字塔模块(RAPM) 2.2.1 空间金字塔注意力(SPA) 2.2.2 金字塔残差块(PRBlock) 2.3 分类器设计 三、关键技术突破 3.1 多尺度特征融合 3.2 轻量化设计策略 3.3 抗噪声…...

【Linux】shell脚本忽略错误继续执行

在 shell 脚本中&#xff0c;可以使用 set -e 命令来设置脚本在遇到错误时退出执行。如果你希望脚本忽略错误并继续执行&#xff0c;可以在脚本开头添加 set e 命令来取消该设置。 举例1 #!/bin/bash# 取消 set -e 的设置 set e# 执行命令&#xff0c;并忽略错误 rm somefile…...

反向工程与模型迁移:打造未来商品详情API的可持续创新体系

在电商行业蓬勃发展的当下&#xff0c;商品详情API作为连接电商平台与开发者、商家及用户的关键纽带&#xff0c;其重要性日益凸显。传统商品详情API主要聚焦于商品基本信息&#xff08;如名称、价格、库存等&#xff09;的获取与展示&#xff0c;已难以满足市场对个性化、智能…...

06 Deep learning神经网络编程基础 激活函数 --吴恩达

深度学习激活函数详解 一、核心作用 引入非线性:使神经网络可学习复杂模式控制输出范围:如Sigmoid将输出限制在(0,1)梯度传递:影响反向传播的稳定性二、常见类型及数学表达 Sigmoid σ ( x ) = 1 1 +...

Spring数据访问模块设计

前面我们已经完成了IoC和web模块的设计&#xff0c;聪明的码友立马就知道了&#xff0c;该到数据访问模块了&#xff0c;要不就这俩玩个6啊&#xff0c;查库势在必行&#xff0c;至此&#xff0c;它来了。 一、核心设计理念 1、痛点在哪 应用离不开数据&#xff08;数据库、No…...

智能分布式爬虫的数据处理流水线优化:基于深度强化学习的数据质量控制

在数字化浪潮席卷全球的今天&#xff0c;数据已成为企业和研究机构的核心资产。智能分布式爬虫作为高效的数据采集工具&#xff0c;在大规模数据获取中发挥着关键作用。然而&#xff0c;传统的数据处理流水线在面对复杂多变的网络环境和海量异构数据时&#xff0c;常出现数据质…...

Angular微前端架构:Module Federation + ngx-build-plus (Webpack)

以下是一个完整的 Angular 微前端示例&#xff0c;其中使用的是 Module Federation 和 npx-build-plus 实现了主应用&#xff08;Shell&#xff09;与子应用&#xff08;Remote&#xff09;的集成。 &#x1f6e0;️ 项目结构 angular-mf/ ├── shell-app/ # 主应用&…...

保姆级教程:在无网络无显卡的Windows电脑的vscode本地部署deepseek

文章目录 1 前言2 部署流程2.1 准备工作2.2 Ollama2.2.1 使用有网络的电脑下载Ollama2.2.2 安装Ollama&#xff08;有网络的电脑&#xff09;2.2.3 安装Ollama&#xff08;无网络的电脑&#xff09;2.2.4 安装验证2.2.5 修改大模型安装位置2.2.6 下载Deepseek模型 2.3 将deepse…...

LRU 缓存机制详解与实现(Java版) + 力扣解决

&#x1f4cc; LRU 缓存机制详解与实现&#xff08;Java版&#xff09; 一、&#x1f4d6; 问题背景 在日常开发中&#xff0c;我们经常会使用 缓存&#xff08;Cache&#xff09; 来提升性能。但由于内存有限&#xff0c;缓存不可能无限增长&#xff0c;于是需要策略决定&am…...

C# 表达式和运算符(求值顺序)

求值顺序 表达式可以由许多嵌套的子表达式构成。子表达式的求值顺序可以使表达式的最终值发生 变化。 例如&#xff0c;已知表达式3*52&#xff0c;依照子表达式的求值顺序&#xff0c;有两种可能的结果&#xff0c;如图9-3所示。 如果乘法先执行&#xff0c;结果是17。如果5…...