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

【仓库设置问题】

问题:

某公司在高速公路一些服务站内开设了百货超市,为了能及时给这些百货超市提供足够的商品,他们需要在一些百货超市旁修建仓库。一个仓库可以同时为多家百货超市提供服务,以满足各个超市对商品的需求。现已知这些百货超市在高速公路上的位置以及需要修建的仓库的数量。请编写程序确定每个仓库修建的位置以及所服务的超市,使所有仓库与所服务的百货超市的距离的总和最小,程序输出所求得的总的最小距离和。

要求仓库必须修在有超市的服务站内不同的仓库必须修在不同的位置,不能修在同一服务站内,在同一服务站内的超市和仓库之间的距离可忽略不计

输入描述:

输入的第一行有两个整数n和k,分别表示超市和仓库的数量,其中1 <= n <= 200, 1 <= k <= 30, k <= n。其后的n行,每一行有一个整数,表示每个超市的位置(相对于高速公路起点的距离)。

输出描述:

输出1行,一个整数,表示所有仓库与所服务的超市的距离的总和。

样例输入:

6 3

5

6

12

19

20

27

样例输出:

8

思路:

采用回溯法

解空间树是子集树。

我们可以在递归分支被目标函数截断后计算最小距离,如果距离小于最佳距离,更新。

代码:

#include<bits/stdc++.h>
using namespace std;int shops, wares;
int result = INT_MAX;int cal(int *shop, int *sign)
{int temp = 0;for(int i = 1; i <= shops; i++){if(!sign[i]){int a = i;int b = i;while(!sign[a] && a != 0) a--;while(!sign[b] && b != shops+1) b++;if(a == 0) temp += shop[b] - shop[i];else if(b == shops+1) temp += shop[i] - shop[a];else if((float)i < float(a+b)/2) temp += shop[i] - shop[a];else temp += shop[b] - shop[i];}}return temp;
}
void dfs(int *shop, int *sign, int cnt)
{if(cnt > wares){int dis = cal(shop, sign);if(dis < result) result = dis;return;}for(int i = 1; i <= shops; i++){if(sign[i]) continue;sign[i] = 1;dfs(shop, sign, cnt+1);sign[i] = 0;}
}
int main()
{cin >> shops >> wares;int *shop = new int[shops+2]();int *sign = new int[shops+2]();for(int i = 1; i <= shops; i++){cin >> shop[i];}sort(shop+1, shop+shops+1);dfs(shop, sign, 1);delete [] shop;delete [] sign;cout << result << endl;return 0;
}

相关文章:

【仓库设置问题】

问题&#xff1a; 某公司在高速公路一些服务站内开设了百货超市&#xff0c;为了能及时给这些百货超市提供足够的商品&#xff0c;他们需要在一些百货超市旁修建仓库。一个仓库可以同时为多家百货超市提供服务&#xff0c;以满足各个超市对商品的需求。现已知这些百货超市在高…...

深度学习知识与心得

目录 深度学习简介 传统机器学习 深度学习发展 感知机 前馈神经网络 前馈神经网络&#xff08;BP网络&#xff09; 深度学习框架讲解 深度学习框架 TensorFlow 一个简单的线性函数拟合过程 卷积神经网络CNN&#xff08;计算机视觉&#xff09; 自然语言处理NLP Wo…...

Qt for Android

文章 USB Qt for android 获取USB设备列表&#xff08;一&#xff09;Java方式 获取 Qt for android 获取USB设备列表&#xff08;二&#xff09;JNI方式 获取 Qt for android 串口库使用 Qt for android : libusb在android中使用 Qt for Android : 使用libusb做CH340x串口传…...

HTTP 的三次握手

​​​​​ HTTP 的三次握手是指在建立 TCP 连接时&#xff0c;客户端和服务器之间进行的三步握手过程。这个过程确保了双方都能够互相通信&#xff0c;并且同步了彼此的序列号和确认号。 概念&#xff1a; 第一次握手&#xff1a;客户端发送一个 SYN&#xff08;同步…...

【Text2SQL 论文】T5-SR:使用 T5 生成中间表示来得到 SQL

论文&#xff1a;T5-SR: A Unified Seq-to-Seq Decoding Strategy for Semantic Parsing ⭐⭐⭐ 北大 & 中科大&#xff0c;arXiv:2306.08368 文章目录 一、论文速读二、中间表示&#xff1a;SSQL三、Score Re-estimator四、总结 一、论文速读 本文设计了一个 NL 和 SQL 的…...

【HarmonyOS】应用屏蔽截屏和录屏

【HarmonyOS】应用屏蔽截屏和录屏 一、问题背景&#xff1a; 金融类或者高密性质的应用APP&#xff0c;对于截屏和录屏场景&#xff0c;某些业务下是禁止不允许。 目前这种场景的需求也是非常有必要的&#xff0c;很多电诈都是通过远程录屏软件&#xff0c;获取到账户密码或者…...

[BUG历险记] ERROR: [SIM 211-100] CSim failed with errors

问题重现 在开发HLS过程中&#xff0c;我碰到一个奇怪的现象&#xff0c;同样的工程&#xff0c;在我重装完系统后&#xff0c;不能进行C仿真了&#xff0c;但是综合实现都是可以正常运作的。 vitis的报错也非常奇怪&#xff0c;单单一行&#xff1a; ERROR: [SIM 211-100] C…...

Redis中大Key与热Key的解决方案

原文地址&#xff1a;https://mp.weixin.qq.com/s/13p2VCmqC4oc85h37YoBcg 在工作中Redis已经成为必备的一款高性能的缓存数据库&#xff0c;但是在实际的使用过程中&#xff0c;我们常常会遇到两个常见的问题&#xff0c;也就是文章标题所说的大 key与热 key。 一、定义 1.1…...

MySQL 视图(2)

上一篇&#xff1a;MySQL视图&#xff08;1&#xff09; 基于其他视图 案例对 WITH [CASCADED | LOCAL] CHECK OPTION 进行释义 创建视图时&#xff0c;可以基于表 / 多个表&#xff0c;也可以使用 其他视图表 / 其他视图 其他视图 的方式进行组合。 总结 更新视图&#x…...

Leecode---技巧---颜色分类、下一个排列、寻找重复数

思路&#xff1a; 遍历一遍记录0,1,2的个数&#xff0c;然后再遍历一次&#xff0c;按照0,1,2的个数修改nums即可。 class Solution { public:void sortColors(vector<int>& nums){int n0 0, n1 0, n2 0;for(int x: nums){if(x0) n0;else if(x1) n1;else n2;}for…...

ERC-7401:嵌套 NFT 标准的全新篇章

在数字资产和区块链技术迅速发展的今天&#xff0c;非同质化代币&#xff08;NFT&#xff09;已经成为了一种重要的资产形式&#xff0c;广泛应用于艺术、游戏、收藏品等多个领域。随着市场需求的多样化&#xff0c;传统的 NFT 标准如 ERC-721 和 ERC-1155 已经不能完全满足用户…...

代码随想录算法训练营Day6| 242.有效的字母异位词、349. 两个数组的交集、202. 快乐数、1. 两数之和

242.有效的字母异位词 知识点补充&#xff1a; 1.遍历HashMap中的值&#xff1a; HashMap<Integer,Integer> map new HashMap<Integer,Integer>(); for(Integer num:map.values()){ } 2.遍历HashMap的键&#xff1a; HashMap<Integer,Integer> map new Ha…...

三十四、openlayers官网示例Dynamic clusters解析——动态的聚合图层

官网demo地址&#xff1a; https://openlayers.org/en/latest/examples/clusters-dynamic.html 这篇绘制了多个聚合图层。 先初始化地图 &#xff0c;设置了地图视角的边界extent&#xff0c;限制了地图缩放的范围 initMap() {const raster new TileLayer({source: new XYZ…...

SpringBoot登录认证--衔接SpringBoot案例通关版

文章目录 登录认证登录校验-概述登录校验 会话技术什么是会话呢?cookie Session令牌技术登录认证-登录校验-JWT令牌-介绍JWT SpringBoot案例通关版,上接这篇 登录认证 先讲解基本的登录功能 登录功能本质就是查询操作 那么查询完毕后返回一个Emp对象 如果Emp对象不为空,那…...

vue3状态管理,pinia的使用

​​​​​​​状态管理 我们知道组件与组件之间可以传递信息&#xff0c;那么我们就可以将一个信息作为组件的独立状态&#xff08;例如&#xff0c;单个组件的颜色&#xff09;或者共有状态&#xff08;例如&#xff0c;多个组件是否显示&#xff09;在组件之传递&#xff0c…...

入门到实践,手把手教你用AI绘画!

前言 一款无需魔法的PS插件&#xff01;下载即用&#xff0c;自带提示词插件&#xff0c;无论你是小白还是大神都能轻松上手&#xff0c;无配置要求&#xff0c;win/mac通通能用&#xff01; AI绘画工具——StartAI 官网&#xff1a;StartAI官网 (istarry.com.cn) 近段时间…...

大模型应用框架-LangChain

LangChain的介绍和入门 &#x1f4a5; 什么是LangChain LangChain由 Harrison Chase 创建于2022年10月&#xff0c;它是围绕LLMs&#xff08;大语言模型&#xff09;建立的一个框架&#xff0c;LLMs使用机器学习算法和海量数据来分析和理解自然语言&#xff0c;GPT3.5、GPT4是…...

探索Linux中的强大文本处理工具——sed命令

探索Linux中的强大文本处理工具——sed命令 在Linux系统中&#xff0c;文本处理是一项日常且重要的任务。sed命令作为一个流编辑器&#xff0c;以其强大的文本处理能力而著称。它允许我们在不修改原始文件的情况下&#xff0c;对输入流&#xff08;文件或管道&#xff09;进行…...

冯喜运:6.3黄金原油晚间最新行情及独家操作策略指导

【黄金消息面分析】&#xff1a;在全球经济的波动和不确定性中&#xff0c;黄金作为传统的避险资产&#xff0c;其价格走势和市场分析一直是投资者关注的焦点。本周一&#xff08;北京时间6月3日&#xff09;&#xff0c;现货黄金价格基本持平&#xff0c;交易商正在等待本周公…...

Spark_SparkOnHive_海豚调度跑任务写入Hive表失败解决

背景 前段时间我在海豚上打包程序写hive出现了一个问题&#xff0c;spark程序向hive写数据时&#xff0c;报了如下bug&#xff0c; org.apache.spark.sql.AnalysisException: The format of the existing table test.xx is HiveFileFormat It doesnt match the specified for…...

ElementUI 年份范围选择器实战:手把手教你封装 el-year-picker 组件(附完整代码)

ElementUI 年份范围选择器实战&#xff1a;手把手教你封装 el-year-picker 组件&#xff08;附完整代码&#xff09; 在后台管理系统开发中&#xff0c;日期选择组件是使用频率极高的功能模块。ElementUI 作为 Vue 生态中最受欢迎的 UI 框架之一&#xff0c;虽然提供了丰富的日…...

MT5 Zero-Shot实战案例:跨境电商多语言商品描述中文初稿生成与改写优化

MT5 Zero-Shot实战案例&#xff1a;跨境电商多语言商品描述中文初稿生成与改写优化 1. 项目概述与核心价值 在跨境电商运营中&#xff0c;商品描述的多语言版本制作是一个耗时耗力的过程。传统方法需要先撰写中文初稿&#xff0c;然后逐条翻译成各种语言&#xff0c;不仅效率…...

专业Steam创意工坊下载解决方案:WorkshopDL跨平台多引擎架构指南

专业Steam创意工坊下载解决方案&#xff1a;WorkshopDL跨平台多引擎架构指南 【免费下载链接】WorkshopDL WorkshopDL - The Best Steam Workshop Downloader 项目地址: https://gitcode.com/gh_mirrors/wo/WorkshopDL WorkshopDL是一款专为技术爱好者和进阶用户设计的跨…...

DS4Windows进阶指南:让PlayStation手柄在PC平台发挥极致性能

DS4Windows进阶指南&#xff1a;让PlayStation手柄在PC平台发挥极致性能 【免费下载链接】DS4Windows Like those other ds4tools, but sexier 项目地址: https://gitcode.com/gh_mirrors/ds/DS4Windows DS4Windows是一款开源工具&#xff0c;专为解决PlayStation手柄在…...

【Linux 物联网网关主控系统-Web部分(四)】

Linux 物联网网关主控系统-Web部分&#xff08;四&#xff09;调用关系总体框架main.htmltop.htmlleft.htmlright.htmlcgi部分调用关系 总体框架 main.html 调用的 HTML&#xff1a; top.html left.html right.html &#xff08;框架集页面&#xff0c;加载顶部、左侧、右侧三…...

SN74181芯片逻辑图解析:从Cn+1进位信号看加法器设计

SN74181芯片逻辑图解析&#xff1a;从Cn1进位信号看加法器设计 在数字电路设计的经典教材中&#xff0c;SN74181算术逻辑单元(ALU)芯片总是占据着重要位置。这款诞生于上世纪60年代的4位ALU芯片&#xff0c;至今仍是理解计算机算术运算基础的绝佳案例。特别是其进位信号Cn1的生…...

Linux系统构建终极指南:从零开始配置虚拟控制台和getty服务

Linux系统构建终极指南&#xff1a;从零开始配置虚拟控制台和getty服务 【免费下载链接】build-linux A short tutorial about building Linux based operating systems. 项目地址: https://gitcode.com/gh_mirrors/bu/build-linux 想要深入了解Linux系统的内部工作原理…...

Phi-3-vision-128k-instruct Ollama国内镜像源加速部署与多模型管理

Phi-3-vision-128k-instruct Ollama国内镜像源加速部署与多模型管理 1. 为什么需要国内镜像源 如果你在国内尝试使用Ollama拉取Phi-3-vision这样的大型模型&#xff0c;可能会遇到下载速度慢甚至失败的问题。这是因为默认的模型仓库位于海外服务器&#xff0c;网络连接不稳定…...

RMBG-2.0(BiRefNet)开源抠图工具落地实操:Streamlit双列界面零门槛上手

RMBG-2.0&#xff08;BiRefNet&#xff09;开源抠图工具落地实操&#xff1a;Streamlit双列界面零门槛上手 想给产品换个背景&#xff0c;却不会用复杂的PS&#xff1f;想快速处理一批图片素材&#xff0c;又担心在线工具泄露隐私&#xff1f;今天&#xff0c;我们就来聊聊一个…...

如何快速解密网易云音乐NCM文件:5分钟掌握完整转换指南

如何快速解密网易云音乐NCM文件&#xff1a;5分钟掌握完整转换指南 【免费下载链接】ncmdump ncmdump - 网易云音乐NCM转换 项目地址: https://gitcode.com/gh_mirrors/ncmdu/ncmdump 还在为网易云音乐下载的加密NCM文件无法在其他播放器上播放而烦恼吗&#xff1f;ncmd…...