当前位置: 首页 > 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…...

CTF show Web 红包题第六弹

提示 1.不是SQL注入 2.需要找关键源码 思路 进入页面发现是一个登录框&#xff0c;很难让人不联想到SQL注入&#xff0c;但提示都说了不是SQL注入&#xff0c;所以就不往这方面想了 ​ 先查看一下网页源码&#xff0c;发现一段JavaScript代码&#xff0c;有一个关键类ctfs…...

基于Flask实现的医疗保险欺诈识别监测模型

基于Flask实现的医疗保险欺诈识别监测模型 项目截图 项目简介 社会医疗保险是国家通过立法形式强制实施&#xff0c;由雇主和个人按一定比例缴纳保险费&#xff0c;建立社会医疗保险基金&#xff0c;支付雇员医疗费用的一种医疗保险制度&#xff0c; 它是促进社会文明和进步的…...

渗透实战PortSwigger靶场-XSS Lab 14:大多数标签和属性被阻止

<script>标签被拦截 我们需要把全部可用的 tag 和 event 进行暴力破解 XSS cheat sheet&#xff1a; https://portswigger.net/web-security/cross-site-scripting/cheat-sheet 通过爆破发现body可以用 再把全部 events 放进去爆破 这些 event 全部可用 <body onres…...

Go 语言接口详解

Go 语言接口详解 核心概念 接口定义 在 Go 语言中&#xff0c;接口是一种抽象类型&#xff0c;它定义了一组方法的集合&#xff1a; // 定义接口 type Shape interface {Area() float64Perimeter() float64 } 接口实现 Go 接口的实现是隐式的&#xff1a; // 矩形结构体…...

Linux简单的操作

ls ls 查看当前目录 ll 查看详细内容 ls -a 查看所有的内容 ls --help 查看方法文档 pwd pwd 查看当前路径 cd cd 转路径 cd .. 转上一级路径 cd 名 转换路径 …...

抖音增长新引擎:品融电商,一站式全案代运营领跑者

抖音增长新引擎&#xff1a;品融电商&#xff0c;一站式全案代运营领跑者 在抖音这个日活超7亿的流量汪洋中&#xff0c;品牌如何破浪前行&#xff1f;自建团队成本高、效果难控&#xff1b;碎片化运营又难成合力——这正是许多企业面临的增长困局。品融电商以「抖音全案代运营…...

服务器--宝塔命令

一、宝塔面板安装命令 ⚠️ 必须使用 root 用户 或 sudo 权限执行&#xff01; sudo su - 1. CentOS 系统&#xff1a; yum install -y wget && wget -O install.sh http://download.bt.cn/install/install_6.0.sh && sh install.sh2. Ubuntu / Debian 系统…...

PAN/FPN

import torch import torch.nn as nn import torch.nn.functional as F import mathclass LowResQueryHighResKVAttention(nn.Module):"""方案 1: 低分辨率特征 (Query) 查询高分辨率特征 (Key, Value).输出分辨率与低分辨率输入相同。"""def __…...

多模态图像修复系统:基于深度学习的图片修复实现

多模态图像修复系统:基于深度学习的图片修复实现 1. 系统概述 本系统使用多模态大模型(Stable Diffusion Inpainting)实现图像修复功能,结合文本描述和图片输入,对指定区域进行内容修复。系统包含完整的数据处理、模型训练、推理部署流程。 import torch import numpy …...

解决:Android studio 编译后报错\app\src\main\cpp\CMakeLists.txt‘ to exist

现象&#xff1a; android studio报错&#xff1a; [CXX1409] D:\GitLab\xxxxx\app.cxx\Debug\3f3w4y1i\arm64-v8a\android_gradle_build.json : expected buildFiles file ‘D:\GitLab\xxxxx\app\src\main\cpp\CMakeLists.txt’ to exist 解决&#xff1a; 不要动CMakeLists.…...