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

小叶OJ 2716: 过河问题 ← 贪心算法

【题目来源】
http://xiaoye.ac.cn/problem.php?id=2716

【题目描述】
有 n 个人要渡河,但只有一条小船,这条小船一次只能坐下最多两个人,并且只有一副船桨。每个人划船的速度不一样,如果两个人一起上船,由于重量变大,划船的速度相当于是划船速度最慢的那个人速度。假设给出每个人单独划船过河所花费的时间 Ti,请问所有人都过河的总时间最短的时间?

【输入格式】
输入两行,第一行是一个整数,表示要过河的 n 个人。
第二行,是 n 个整数,按速度从快到慢排序好的每个人划船过河的时间。

【输出格式】
输出一行,给出所有人过河所花费最短的时间。

【输入样例】
4
1 2 5 10

【输出样例】
17

【算法分析】
● 将各个过河时间从小到大排序并存在数组 a 中,当 n≥4 时,过河方案为:
方案一:
最快的和次快的过河,然后最快的回来,再次慢的和最慢的过河,然后次快的回来。时间为 a[1]+2*a[2]+a[n]
方案二:
最快的和最慢的过河,然后最快的回来,再最快的和次慢的过河,然后最快的回来。时间为 2*a[1]+a[n-1]+a[n]
根据比较结果,将所选方案的时间累加到总时间 s 中,并将人数 n 减少 2,因为每次循环处理了两个人过河。

【算法代码】

#include <bits/stdc++.h>
using namespace std;int main() {int n;cin>>n;int a[n+5];for(int i=1; i<=n; i++) cin>>a[i];sort(a+1,a+n+1);int s=0;while(n>=4) {if(2*a[1]+a[n-1]+a[n]>2*a[2]+a[1]+a[n]) {s+=2*a[2]+a[1]+a[n];} else s+=2*a[1]+a[n-1]+a[n];n-=2;}if(n==3) s+=a[1]+a[2]+a[3];else if(n==2) s+=a[2];else s+=a[1];cout<<s<<endl;return 0;
}/*
in:
4
1 2 5 10out:
17
*/





【参考文献】
https://blog.csdn.net/u013596478/article/details/105016223

https://mp.weixin.qq.com/s/a9Y2YTpjjmdv2JzI3EtAVw

相关文章:

小叶OJ 2716: 过河问题 ← 贪心算法

【题目来源】http://xiaoye.ac.cn/problem.php?id2716【题目描述】 有 n 个人要渡河&#xff0c;但只有一条小船&#xff0c;这条小船一次只能坐下最多两个人&#xff0c;并且只有一副船桨。每个人划船的速度不一样&#xff0c;如果两个人一起上船&#xff0c;由于重量变大&am…...

LeetCode509:斐波那契数列

代码如下 class Solution { public:int fib(int n) {//这个是为了特殊n&#xff0c;当n 0时&#xff0c; 当 n 1时。if(n 0) return 0;if(n 1) return 1;//第一次开dp专题&#xff0c;连dp数组都忘记定义了。只写了下面&#xff0c;哭vector<int> dp(n 1, 0);dp[…...

5G前传-介绍

1. 引用 知识分享系列一&#xff1a;5G基础知识-CSDN博客 5G前传的最新进展-CSDN博客 灰光和彩光_通信行业5G招标系列点评之二&#xff1a;一文读懂5G前传-光纤、灰光、彩光、CWDM、LWDM、MWDM...-CSDN博客 术语&#xff1a; 英文缩写描述‌BBU&#xff1a;Building Baseba…...

【Python机器学习】循环神经网络(RNN)——超参数

几乎所有模型都可以根据数据和样本进行调整&#xff0c;它们都有各自的优势和相应的利弊权衡方式。寻找最优超参数集通常是一个棘手的问题&#xff0c;但是人类的直觉和经验可以为我们提供解决问题的方法。比如之前的例子&#xff1a; #设置任意输入序列的最大长度 maxlen100 …...

【Android 13源码分析】WindowContainer窗口层级-1-初识窗口层级树

在安卓源码的设计中&#xff0c;将将屏幕分为了37层&#xff0c;不同的窗口将在不同的层级中显示。 对这一块的概念以及相关源码做了详细分析&#xff0c;整理出以下几篇。 【Android 13源码分析】WindowContainer窗口层级-1-初识窗口层级树 【Android 13源码分析】WindowCon…...

Node.js的学习2——内置模块(一)

Node.js的内置模块 module模块global全局变量Console控制台Errors错误模块捕获异常异步方法通过回调函数传递异常事件触发器对象异常捕获 module模块 使用module模块可以查看Node.js所有的内置模块、在所有模块中都可以使用的全局变量、程序在运行过程中可能会出现的四类错误。…...

信息安全工程师(5)域名与域名解析

一、域名 1. 定义与功能 域名&#xff08;Domain Name&#xff09;是互联网上用于标识网站或服务器地址的名称&#xff0c;由一串由点分隔的字符组成&#xff0c;如“example.com”。域名的主要功能是提供一种便于记忆和输入的地址形式&#xff0c;以代替难以记忆的IP地址。域名…...

idear导入他人项目如何快速运行

最近idear经常导入别人的项目&#xff0c;结果永远在加载依赖项。网上查了一堆资料&#xff0c;什么jdk问题&#xff0c;环境变量问题&#xff0c;maven仓库路径问题&#xff0c;总之就是没啥用。那有没有什么简单粗暴的办法&#xff0c;能够导入项目后快速运行呢。 解决方法&a…...

直流无刷电机霍尔线序自学习解释

直流无刷电机霍尔线序自学习 步骤详解 1. 初始连接 连接电机的三相线&#xff1a;A、B、C。连接霍尔传感器线&#xff1a;HA、HB、HC。 2. 输入电压组合与霍尔信号记录 电机的电压输入组合和霍尔信号记录是电机控制系统中至关重要的一部分&#xff0c;它们决定了电机的运转…...

C++学习笔记(26)

七 、显示字符串中的字符 从界面上输入一个字符串&#xff08;C 风格&#xff09;&#xff0c;把字符串中的每个字符显示出来&#xff0c;如果输入的是"abc"&#xff0c;要求&#xff1a; 1&#xff09;正序显示&#xff1a;a b c 2&#xff09;逆序显示&#xff1a;…...

安卓14剖析SystemUI的ShadeLogger/LogBuffer日志动态控制输出dumpsy机制

背景&#xff1a; 看SystemUI的锁屏相关代码时候发现SystemUI有一个日志打印相关的方法调用&#xff0c;相比于常规的Log.i直接可以logcat查看方式还是比较新颖。 具体日志打印代码如下&#xff1a; 下面就来介绍一下这个ShadeLogger到底是如何打印的。 分析源码&#xff1…...

华为CNA VRM搭建(使用vmware worfstartion搭建)

创建虚拟机&#xff1a; 自定义→高级 选择硬件兼容性&#xff1a;默认安装版本&#xff0c;如果未来想要将此虚拟机安装到其他电脑&#xff0c;其他电脑版本过低&#xff0c;此时可以向下兼容&#xff0c;这里我们默认版本 稍后安装操作系统&#xff1a; CNA采用Euler OS系统…...

【WRF工具】WRF Domain Wizard第二期:使用教程

【WRF工具】WRF Domain Wizard第二期&#xff1a;使用教程 WRF Domain Wizard使用教程1&#xff09;Wizard Option&#xff1a;新建区域/打开已有区域2&#xff09;New Domain&#xff1a;新建区域3&#xff09;Horizontal Editor&#xff1a;水平编辑器4&#xff09;Namelist.…...

智能摄像头MP4格式化恢复方法

如果说生孩子扎堆&#xff0c;那很显然最近智能摄像头多碎片的恢复也扎堆了&#xff0c;这次恢复的是一个不知名的小品牌。其采用了mp4视频文件方案&#xff0c;不过这个案例的特殊之处在于其感染了病毒且不只一次&#xff0c;我们来看看这个小品牌的智能恢复头格式化的恢复方法…...

【C++】unordered系列

前言&#xff1a; 在C11及以后的标准中&#xff0c;unordered容器是标准模板库&#xff08;STL&#xff09;的一部分&#xff0c;提供了高效的数据结构选项&#xff0c;适用于需要快速查找和插入操作的场景。 unordered通常与关联容器一起使用&#xff0c;特别是unordered_map和…...

Cobbler 搭建方法

统信服务器操作系统行业版V20-1000c【Cobbler 搭建】手册 统信服务器操作系统行业版 V20版本上Cobbler 搭建方法 文章目录 功能概述一、使用范围二、cobbler工作流程1. Server 端2. Client 端三、 环境准备1. 测试环境告知,以提供配置时参考:2. 关闭防火墙、selinux:3. 注意…...

从边缘到云端,合宙DTURTU打造无缝物联网解决方案

随着物联网&#xff08;IoT&#xff09;技术的飞速发展&#xff0c;万物互联的时代已经到来&#xff0c; 如何高效、稳定地连接边缘设备与云端平台&#xff0c;实现数据的实时采集、传输与处理&#xff0c;成为了推动物联网应用落地的关键。 DTU&#xff08;数据传输单元&…...

【Android Studio】API 29(即Android 10)或更高版本,在程序启动时检查相机权限,并在未获取该权限时请求它

文章目录 1. 在AndroidManifest.xml文件中&#xff0c;声明相机权限&#xff1a;2. 在你的Activity中&#xff08;例如MainActivity&#xff09;测试 1. 在AndroidManifest.xml文件中&#xff0c;声明相机权限&#xff1a; <uses-feature android:name"android.hardwar…...

【裸机装机系列】3.kali(ubuntu)-更新sources.list并重启

当装机并重启计算机后&#xff0c;暂时还不能使用&#xff0c;需要更新源并下载软件 1、更新软件源 1> 切换root使用命令 sudo su root 进入界面后&#xff0c;是你自己的账户&#xff0c;不是root账户&#xff0c;这里的操作是需要进入root账户进行操作的&#xff0c;否…...

text2sql(NL2Sql)综述《The Dawn of Natural Language to SQL: Are We Fully Ready?》

《The Dawn of Natural Language to SQL: Are We Fully Ready?》(github)出自2024年6月的NL2SQL(Natural language to SQL )综述论文。这篇论文尝试回答如下三个问题&#xff1a; 问题1:NL2SQL的现状是什么&#xff1f;(Q1:Where Are we Now?) 论文图1总结了近20年NL2SQL方法…...

告别PWM!用STM32串口轻松驱动幻尔16路舵机控制板(附完整代码)

STM32串口驱动幻尔16路舵机控制板的实战指南 从PWM到串口&#xff1a;舵机控制的技术演进 记得我第一次尝试用STM32控制机械臂时&#xff0c;光是配置PWM定时器就花了两天时间。每个舵机需要独立的PWM通道&#xff0c;复杂的定时器分频计算&#xff0c;还有那令人头疼的占空比换…...

Xilinx Aurora 8B/10B IP核(5):GT资源规划实战——从PCB引脚到IP核Lane的映射法则

1. 从PCB引脚到IP核Lane的映射挑战 刚接触Xilinx Aurora 8B/10B IP核配置时&#xff0c;最让我头疼的就是这个"物理到逻辑"的映射问题。记得第一次调试时&#xff0c;明明IP核配置界面显示链路已建立&#xff0c;但实际硬件就是无法通信&#xff0c;后来发现是Lane分…...

Kook Zimage真实幻想Turbo常见问题解决:生成全黑图?显存不足?看这篇就够了

Kook Zimage真实幻想Turbo常见问题解决&#xff1a;生成全黑图&#xff1f;显存不足&#xff1f;看这篇就够了 你是不是已经迫不及待地部署好了Kook Zimage真实幻想Turbo&#xff0c;准备大展身手创作奇幻大片&#xff0c;结果一运行&#xff0c;要么生成一张全黑的图片&#…...

BilibiliDown终极指南:3步轻松下载B站视频的完整教程

BilibiliDown终极指南&#xff1a;3步轻松下载B站视频的完整教程 【免费下载链接】BilibiliDown (GUI-多平台支持) B站 哔哩哔哩 视频下载器。支持稍后再看、收藏夹、UP主视频批量下载|Bilibili Video Downloader &#x1f633; 项目地址: https://gitcode.com/gh_mirrors/bi…...

AI建站工具哪家强?看懂这份选型标准与对比指南再做决定

面对市面上五花八门的AI建站工具&#xff0c;很多人陷入选择困难&#xff1a;有的号称全智能生成&#xff0c;有的强调设计感强&#xff0c;有的主打SEO友好。到底哪款适合自己&#xff1f;抛开品牌和营销话术&#xff0c;真正需要看懂的&#xff0c;是工具背后的底层逻辑和核心…...

革命性Vue动画库@vueuse/motion:10分钟实现惊艳交互动效

革命性Vue动画库vueuse/motion&#xff1a;10分钟实现惊艳交互动效 【免费下载链接】motion &#x1f939; Vue Composables putting your components in motion 项目地址: https://gitcode.com/gh_mirrors/moti/motion vueuse/motion 是一个革命性的Vue动画库&#xff…...

探索SillyTavern:重新定义AI角色交互体验的开源平台

探索SillyTavern&#xff1a;重新定义AI角色交互体验的开源平台 【免费下载链接】SillyTavern LLM Frontend for Power Users. 项目地址: https://gitcode.com/GitHub_Trending/si/SillyTavern 在人工智能与人类交互日益紧密的今天&#xff0c;如何打破传统聊天界面的局…...

Seata 1.6.1 + Nacos配置避坑指南:Windows环境从安装到整合SpringBoot的完整链路

Seata 1.6.1与Nacos深度整合实战&#xff1a;Windows环境下的全链路配置精要 当微服务架构遇上分布式事务&#xff0c;Seata无疑是Java开发者手中的瑞士军刀。但在Windows环境下&#xff0c;从零搭建Seata服务端到与SpringBoot应用无缝集成&#xff0c;这条路上布满的配置陷阱足…...

Isaac Sim 6 利用Replicator实现高效语义分割与实例分割(实践指南5.10)

1. 为什么选择Isaac Sim生成分割数据集&#xff1f; 在计算机视觉项目中&#xff0c;语义分割和实例分割是两项基础但极其耗时的任务。传统的数据标注方式需要人工逐像素标注&#xff0c;一个1000张图片的数据集可能需要团队花费数周时间。而使用Isaac Sim的Replicator工具&…...

新手福音:通过快马生成wsl2入门项目,轻松迈出linux开发第一步

作为一个刚接触Linux开发的新手&#xff0c;我最近在尝试使用WSL2搭建开发环境时遇到了不少麻烦。从安装配置到基础命令学习&#xff0c;每一步都让我这个Windows用户感到手足无措。直到发现了InsCode(快马)平台&#xff0c;它帮我生成了一套完整的WSL2入门项目&#xff0c;让我…...