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

2025年3月电子学会等级考试五级题——4、收费站在哪里

news 来源：原创 2025/8/12 16:01:54

文章目录

- 题目
- 代码
- 公式
- 小结

题目

4、收费站在哪里
在一条高速公路上，如果已知 n 座收费站的位置 x1,x2,… ,xn（不妨假设 0=x1 ≤ x2 ≤ … ≤ xn），就很容易算出一共有 n(n-1)/2 个距离的值。而比较困难的问题是，在收集了一大堆过路费发票后，我们筛选出了 n(n-1)/2 个距离的值，现在想知道收费站都分布在哪里？
当然对应一组距离值，可能有多组解，你只要输出任何一个即可。
时间限制：1000
内存限制：65536
输入
输入第一行给出正整数 m（< 50），即距离值的数量。随后一行给出 m 个距离，均为 int 范围内的正整数。
输出
按坐标值升序列出所有收费站的位置，其中 x1=0。同行数字间以 1 个空格分隔，行首尾不得有多余空格。注：题目保证所有坐标为 int 范围内的非负整数。
样例输入
10
3 4 6 8 1 3 5 2 4 2
样例输出
0 2 4 5 8

代码

#include <bits/stdc++.h>
using namespace std;
int n,//收费站数 m,//距离数量 maxd,//d;
vector<int> sta;//向量容器（动态数组）存放收费站 
multiset<int,greater<int>> dis;//可以重复元素，自动排序的关联容器，用来存放收费站间距离 
//共num个数，从x开始，dis是剩余的距离，sta是认定的收费站 
void view(string s,multiset<int,greater<int>>& dis,vector<int>& sta){cout<<s<<endl;cout<<"所剩距离：\n";for(auto i=dis.begin();i!=dis.end();i++)cout<<*i<<"\t";cout<<endl;cout<<"已有站点：\n";for(auto i=sta.begin();i!=sta.end();i++)cout<<*i<<"\t";cout<<endl;
}
//递归，深搜，找到n-2个合格收费站
//4个参数，分别是：1已明确收费站数，2已经明确的距离（往后要找小于等于的）
//3关联容器，存放剩余的距离； 4向量容器，已经明确的收费站 
bool go(int num,int x,multiset<int,greater<int>> dis,vector<int>& sta){cout<<"收费站数"<<num<<"\t需要"<<n<<endl;view("出发",dis,sta);if(num==n){//目标：凑够n个收费站cout<<"ok!!!!!!!!!!!!!!!!!\n";return 1;}//比x(上个)小的剩余距离作为站点，开始尝试 for(multiset<int,greater<int>>::iterator i=dis.lower_bound(x);i!=dis.end();i++){cout<<"剩余距离："<<*i<<"\t";multiset<int,greater<int>> disb=dis;//拷贝剩余距离 bool k=1;//先设定该距离可以作为收费站 for(vector<int>::iterator j=sta.begin();j!=sta.end();j++){//遍历已有收费站 cout<<"到站点"<<*j<<"的距离"<<abs(*j-*i);//判定该收费站和已有收费站的间距都存在 if(disb.find(abs(*j-*i))==disb.end()){k=0;cout<<"没有\n";break;} else cout<<"有\n"<<endl; }//如果间距都有，剔除这些间距 if(k){for(vector<int>::iterator j=sta.begin();j!=sta.end();j++)disb.erase(disb.find(abs(*j-*i)));//清除该收费站产生的距离 sta.push_back(*i);//多了个收费站 //sort(sta.begin(),sta.end());view("搞定一个",disb,sta);if(go(num+1,*i,disb,sta))return 1;//递归 sta.pop_back();//回溯 }else cout<<"该收费站不存在!\n";}cout<<"失败!\n";return 0;
}
int main(){freopen("data.cpp","r",stdin);cin>>m;//共几个距离 for(int i=1;i<=m;i++){cin>>d;dis.insert(d);//收费站间距放进关联容器，能自动排序 maxd=max(d,maxd);//得到最大距离 }n=(1+sqrt(1+8*m))/2;//n(n-1)/2=m,推出一元二次方程n^2-n-2*m=0;得到解 sta.push_back(0),sta.push_back(maxd);//可以明确0和最大距离始末两个收费站，放进vector sort(sta.begin(),sta.end());multiset<int,greater<int>>::iterator x=dis.find(maxd);dis.erase(x);//已经明确最大距离是最后一个收费站，剔除间距集合 view("开始",dis,sta);if(go(2,maxd,dis,sta)){//递归，深搜，找到合格的n-2个收费站 sort(sta.begin(),sta.end());//升序输出所有收费站 for(auto i=sta.begin();i!=sta.end();i++)cout<<*i<<" ";}return 0;
}

公式

在这里插入图片描述

小结

1.以前只用queue、vector、priority queue,现在用multiset，还是挺好用的。
2.multiset<int,greater> dis;第一个参数是存储元素类型，第二个参数是比较函数对象。
3.insert、erase、find，需要操作迭代器对象（类似于指针）。

2025年3月电子学会等级考试五级题——4、收费站在哪里

文章目录题目代码公式小结题目 4、收费站在哪里在一条高速公路上，如果已知 n 座收费站的位置 x1,x2,… ,xn（不妨假设 0x1 ≤ x2 ≤ … ≤ xn），就很容易算出一共有 n(n-1)/2 个距离的值。而比较困难的问题是，在收集…...

编程日记 2025/8/12 16:01:54

深入探索 JavaScript 中的模块对象

引言在现代 JavaScript 开发中，模块化编程是一项至关重要的技术。它允许开发者将代码拆分成多个独立的模块，每个模块专注于单一功能，从而提高代码的可维护性、可测试性和复用性。而模块对象则是模块化编程中的核心概念之一，它为…...

编程日记 2025/8/10 20:36:11

R1-Searcher：用强化学习解锁大语言模型检索新能力！

R1-Searcher：用强化学习解锁大语言模型检索新能力！ 大语言模型（LLMs）发展迅猛，却常因依赖内部知识而在复杂问题上“栽跟头”。今天解读的论文提出R1-Searcher框架，通过强化学习提升LLMs检索能力。它表现超…...

编程日记 2025/8/9 7:32:37

LangChain框架-PromptTemplate 详解

摘要本文聚焦于 LangChain 框架中PromptTemplate提示词模板模块的深度解析，主要参考langchain_core.prompts源码模块与官方文档。系统梳理 LangChain 对提示词模板的封装逻辑与设计思路，旨在帮助读者构建全面、深入的知识体系，为高效运用LangChain 框架的提示词模板开发应用…...

编程日记 2025/8/9 11:24:50

【Java ee 初阶】文件IO和操作（下）

书接上文文本操作的方法 String[] list() 返回 File 对象代表的目录下的所有文件名 File[] listFiles() 返回 File 对象代表的目录下的所有文件，以 File 对象表示此处是针对File对象打印得到的效果（调用了File的toString） boolean …...

编程日记 2025/8/8 22:15:23

Android7 Input（六）InputChannel

概述: 本文讲述Android Input输入框架中 InputChannel的功能。从前面的讲述，我们知道input系统服务最终将输入事件写入了InputChannel，而input属于system_server进程，App属于另外一个进程，当Input系统服务想要把事件传递给App进行…...

编程日记 2025/8/7 20:34:01

【Java ee初阶】初始网络

一、IP地址概念 IP地址主要用于标识网络主机、其他网络设备（如路由器）的网络地址。简单说，IP地址用于定位主机的网络地址。就像我们发送快递一样，需要知道对方的收货地址，快递员才能将包裹送到目的地。格式 IP…...

编程日记 2025/8/12 16:01:51

LabVIEW 2019 与 NI VISA 20.0 安装及报错处理

在使用 Windows 11 操作系统的电脑上，同时安装了 LabVIEW 2019 32 位和 64 位版本的软件。此前安装的 NI VISA 2024 Q1 版，该版本与 LabVIEW 2019 32 位和 64 位不兼容，之后重新安装了 NI VISA 20.0。从说明书来看，NI VISA 20.0 …...

编程日记 2025/8/7 20:33:58

http协议理解

文章目录 http协议理解基本概念HTTP版本演变版本编年史版本对比未来趋势 HTTP请求/响应结构请求报文响应报文HTTP方法分类对比方法选择原则必须遵守的约束常见状态码HTTP头部字段HTTPSHTTPS 核心功能说明HTTPS 如何工作？ HTTP特点补充知识点启用HTTP/2Nginx 中配置…...

编程日记 2025/8/7 20:33:56

typecho中的Widget设计文档

组成系统的最基本元素什么是Widget Widget是组成Typecho的最基本元素，除了已经抽象出来的类库外，其它几乎所有的功能都会通过Widget来完成。在实践中我们发现，在博客这种小型但很灵活的系统中实施一些大型框架的思想是不合适的&#xff0c…...

编程日记 2025/8/11 17:27:31

使用ESPHome烧录固件到ESP32-C3并接入HomeAssistant

文章目录一、安装ESPHome二、配置ESP32-C3控制灯1.主配置文件esp32c3-luat.yaml2.基础通用配置base.yaml3.密码文件secret.yaml4.围栏灯four_light.yaml5.彩灯rgb_light.yaml6.左右柱灯left_right_light.yaml 三、安装固件四、HomeAssistant配置ESPHome1.直接访问2.配置ESPHom…...

编程日记 2025/8/8 21:32:12

基于STM32、HAL库的CH340N USB转UART收发器驱动程序设计

一、简介： CH340N是南京沁恒电子生产的一款USB转串口芯片，具有以下特点：支持USB 2.0全速（12Mbps）内置时钟，无需外部晶振支持5V和3.3V电源电压提供常用的MODEM联络信号内置上电复位电路支持Windows/Linux/Mac OSX等多平台驱动体积小，SOP-8封装二、硬件接口： CH…...

编程日记 2025/8/9 9:54:48

Spring Boot Controller 如何处理HTTP请求体

Spring Boot (通过Spring MVC) 提供了强大的机制来处理不同 Content-Type 的HTTP请求体。这主要依赖于 HttpMessageConverter 接口的各种实现，它们能够自动将请求体内容转换成Java方法参数。一、核心机制：HttpMessageConverter Spring MVC会根据…...

编程日记 2025/8/11 22:20:50

【deepseek教学应用】001：deepseek如何撰写教案并自动实现word排版

本文讲述利用deepseek如何撰写教案并自动实现word高效完美排版。文章目录一、访问deepseek官网二、输入教案关键词三、格式转换四、word进一步排版一、访问deepseek官网官网：https://www.deepseek.com/ 进入主页后，点击【开始对话】，如…...

编程日记 2025/8/12 16:01:53

【Spring Boot 多模块项目】@MapperScan失效、MapperScannerConfigurer 报错终极解决方案

在使用 Spring Boot 构建多模块项目，集成 MyBatis-Plus 时，很多开发者会遇到类似如下启动报错： Error creating bean with name mapperScannerConfigurer ... Caused by: java.lang.IllegalArgumentException: Property basePackage is requ…...

编程日记 2025/8/12 16:00:36

vue 中如何使用region？

vue 中如何使用region？ 在 Vue 文件中，你可以使用 //#region 和 //#endregion 注释来创建可折叠的代码区块（类似于 C# 的 region）。这可以显著提高大型 Vue 组件的可读性。 1. 基本用法在 <script> 部分使用 <script&…...

编程日记 2025/8/11 6:44:06

Spring Boot 启动原理的核心机制

一、核心启动流程概览 Spring Boot 的启动流程可概括为 7 个关键阶段： 1. 加载启动类 (Main Class) 2. 初始化 SpringApplication 实例 3. 加载配置 & 准备环境 (Environment) 4. 创建 ApplicationContext（容器） 5. 刷新容器&#…...

编程日记 2025/8/11 3:54:16

【每天学习一点点】使用Python的pathlib模块分割文件路径

使用Python的pathlib模块分割文件路径 pathlib模块（Python 3.4）提供了面向对象的文件系统路径操作方式，比传统的os.path更加直观和易用。以下是使用pathlib分割文件路径的几种方法： 基本路径分割 from pathlib import Path# 创…...

编程日记 2025/8/9 13:17:13

Qt/C++面试【速通笔记八】—Qt的事件处理机制

在Qt中，事件处理机制是应用程序与用户或系统交互的核心。通过事件处理，Qt能够响应用户的输入、窗口的变化、定时器的触发等各种情况。 1. 事件循环（Event Loop） 在Qt应用程序中，事件循环是事件处理机制的基础。事件循…...

编程日记 2025/8/7 22:07:43

uniapp自定义步骤条(可二开进行调试)

前言有一个业务需求是需要一个步骤条，但是发现开源的都不太合适，所以就自己写了一个。开始 test.vue <template><view class"authenticateRecordDetails_container"><view class"authenticateSte…...

编程日记 2025/8/12 2:11:43

uniapp｜实现多终端聊天对话组件、表情选择、消息发送

基于UniApp框架，实现跨平台多终端适配的聊天对话组件开发、表情选择交互设计及消息发送，支持文本与表情混合渲染。目录聊天界面静态组件实现消息列表布局消息气泡双向布局辅助元素定位与样式静态数据模拟与扩展性设计表情选择器静态模块浮层实现符号网格排列多端样式适配方…...

编程日记 2025/8/7 22:07:39

1.3.1 Linux音频框架alsa详细介绍

ALSA作为对旧OSS系统的替代方案，始于1998年。当时OSS还闭源商业化，因此社区开始开发开源的ALSA。经过多年的发展，ALSA成为Linux内核中音频架构的标准。结构和架构 ALSA由以下几个主要部分组成： 内核模块： 这是ALSA的…...

编程日记 2025/8/12 10:58:52

R 语言机器学习：为遥感数据处理开启新视角

技术点目录基础理论、机器学习与数据准备建模与空间预测实践案例与项目了解更多 ——————————————————————————————————————————— 前言综述在当今科技快速发展的时代，遥感技术为生态学研究提供了海量的数据资源&#xf…...

编程日记 2025/8/11 18:17:31

深度 |提“智”向新，奔向未来——当前机器人产业观察

机器人踏着“猫步”在T台走秀、进入工厂协助造车，教育、医疗、城市管理等领域都有了机器人的帮助……今天，机器人已得到广泛应用，走进你我的生活。伴随着技术日新月异，机器人产业加快提“智”向新。特别是今年以来&#xf…...

编程日记 2025/8/12 6:40:11

Web开发-JavaEE应用SpringBoot栈ActuatorSwaggerHeapDump提取自动化

知识点： 1、安全开发-JavaEE-常见依赖-Actuator&Swagger 2、安全开发-JavaEE-安全问题-配置安全&接口测试一、演示案例-WEB开发-JavaEE-监控依赖-SpringBoot&Actuator&配置安全 SpringBoot Actuator模块提供了生产级别的功能，比如健康…...

编程日记 2025/8/11 3:57:39

AI Agent开发之门：微软官方课程全面解析

AI Agent开发之门：微软官方课程全面解析引言项目概览10 节核心课程内容详解1. AI 代理简介及应用场景2. 探索 AI Agentic 框架3. 理解 AI Agentic 设计模式4. 工具使用设计模式5. Agentic RAG（检索增强生成）6. 构建可信赖的 AI Agents7. 规划…...

编程日记 2025/8/11 3:04:16

Unity-Shader详解-其五

关于Unity的Shader部分的基础知识其实已经讲解得差不多了，今天我们来一些实例分享： 溶解效果如下： 代码如下： Shader "Chapter8/chapter8_1" {Properties{// 定义属性[NoScaleOffset]_Albedo("Albedo", 2…...

编程日记 2025/8/7 22:07:27

从零打造个人博客静态页面与TodoList应用：前端开发实战指南

前言在当今数字时代，拥有个人博客和高效的任务管理工具已成为开发者展示自我和提升生产力的标配。本文将带你从零开始，通过纯前端技术实现一个兼具个人博客静态页面和TodoList任务管理功能的综合应用。无论你是前端新手还是希望巩固基础的中级开发者&a…...

编程日记 2025/8/7 20:10:22

开发者如何优雅应对HTTPS抓包难题

开发者如何优雅应对HTTPS抓包难题：工具实战深度解析调试HTTPS接口这件事，真是程序员永远的痛。特别是在移动端、或者遇到客户端集成了第三方安全SDK的项目时，网络调试的门槛几乎成倍提升。你可能也遇到过：Charles不识别证书、…...

编程日记 2025/8/7 22:07:23

Ubuntu 安装远程桌面连接RDP方式

1. 安装 XFCE4 桌面环境如果你的 Ubuntu 系统默认使用 GNOME 或其它桌面环境，可以安装轻量级的 XFCE4： sudo apt update sudo apt install xfce4 xfce4-goodies 说明：xfce4-goodies 包含额外的插件和工具（如面板插件、终端等&a…...

编程日记 2025/8/7 22:07:21

Ubuntu 22.04 出现 ‘Temporary failure resolving‘ 解决方案

a、使用apt 安装 resolvconf sudo apt-get install resolvconf b、使用 cd /etc/resolvconf/resolv.conf.d/ 进入文件夹，使用 ls 查看目录，会显示 base head tail c、使用 sudo vim base 编辑base文件， 进入时为空，添加 name…...

编程日记 2025/8/12 9:36:10

ubuntu 22.04 换源

参考：清华大学开源软件镜像站 ubuntu | 镜像站使用帮助 | 清华大学开源软件镜像站 | Tsinghua Open Source Mirror...

编程日记 2025/8/7 22:07:17

Java并发编程几个问题的解答

目录 1、以前你编写的Java程序同时能做几件事情？有几个执行流程？main方法执行完，整个程序一定会退出吗？2、早期的电脑一般是单核CPU，但那时我们就可以在编写程序的同时听歌，你觉得其CPU可以同时执行两个程序…...

编程日记 2025/8/7 22:07:14

JavaScript中数组和对象不同遍历方法的顺序规则

在JavaScript中，不同遍历方法的顺序规则和适用场景存在显著差异。以下是主要方法的遍历顺序总结： 一、数组遍历方法 for循环 • 严格按数组索引顺序遍历（0 → length-1） • 支持break和continue中断循环 • 性能最优，…...

编程日记 2025/8/7 22:07:13

C++ STL入门：set 集合容器

C STL入门：set 集合容器一、核心特性与适用场景 set 是 C STL 提供的关联式容器，基于红黑树实现，具有两大核心特性： 特性表现形式底层原理元素唯一性重复值自动去重插入时进行二叉树键比对自动排序元素默认升序排列红黑树中序遍…...

编程日记 2025/8/7 22:07:11

[论文笔记] 超详细解读DeepSeek v3全论文技术报告

DeepSeek-V3是一个强大的专家混合（Mixture-of-Experts，MoE）语言模型，总共671B参数，每个token激活37B参数（可以理解为有多个专家，但每个token只会选择一部分专家进行推理，所以一个token的预测，只会用到37B参数），DeepSeek-V3 使用了多头潜在注意力（...

编程日记 2025/8/7 22:07:09

JS 问号（？）运算符避免中间报错

一、场景在前端开发过程中，有一些情况比如某些属性可能由于渲染数据的时机不同，一开始是null 或者undifine, 这样访问下面的属性的时候就会报错，我们可以给每个层级后面加个? 就可以避免这个错误。 let data {user: {profile: {name: &q…...

编程日记 2025/8/11 8:42:46

4：点云处理—去噪、剪切、调平

1.点云去噪 dev_clear_window ()dev_open_window(0, 0, 560, 560, black, WindowHandle)GenParamNames : [lut,intensity,light_position,disp_pose,alpha]GenParamValues : [color1,coord_z,0.0 0.0 -0.3 1.0,true,1]DispPose : [0,-0.0005,717.04,280,0,20,0]Instructions[0]…...

编程日记 2025/8/7 17:16:01

文章目录

题目

代码

公式

小结

相关文章：