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

新手必看!圣女司幼幽-造相Z-Turbo开箱即用,3步生成精美古风人像

新手必看&#xff01;圣女司幼幽-造相Z-Turbo开箱即用&#xff0c;3步生成精美古风人像 你是不是也遇到过这样的烦恼&#xff1a;脑子里构思好了一位仙气飘飘的古风角色&#xff0c;但要么自己不会画&#xff0c;要么用普通AI工具生成的效果总差那么点意思——衣服质感像塑料&…...

3步实现全适配界面:Vant Weapp组件库无障碍设计指南

3步实现全适配界面&#xff1a;Vant Weapp组件库无障碍设计指南 【免费下载链接】vant-weapp 轻量、可靠的小程序 UI 组件库 项目地址: https://gitcode.com/gh_mirrors/va/vant-weapp 无障碍设计是现代应用开发的核心要求&#xff0c;它不仅能让应用覆盖更广泛的用户群…...

e1547:如何构建高效的内容过滤与社区浏览体验

e1547&#xff1a;如何构建高效的内容过滤与社区浏览体验 【免费下载链接】e1547 A sophisticated e621 browser 项目地址: https://gitcode.com/gh_mirrors/e1/e1547 在当今数字内容爆炸的时代&#xff0c;用户面临着信息过载的挑战&#xff0c;尤其是在兴趣社区中&…...

突破单机限制:PlugY重塑暗黑破坏神2游戏体验的五大维度升级

突破单机限制&#xff1a;PlugY重塑暗黑破坏神2游戏体验的五大维度升级 【免费下载链接】PlugY PlugY, The Survival Kit - Plug-in for Diablo II Lord of Destruction 项目地址: https://gitcode.com/gh_mirrors/pl/PlugY 一、单机玩家的困境与破局之道 在暗黑破坏神…...

Palworld存档工具终极指南:掌握游戏数据编辑的专业方法

Palworld存档工具终极指南&#xff1a;掌握游戏数据编辑的专业方法 【免费下载链接】palworld-save-tools Tools for converting Palworld .sav files to JSON and back 项目地址: https://gitcode.com/gh_mirrors/pa/palworld-save-tools 你是否曾想过深入Palworld游戏…...

告别手动回复!用Python+uiautomation2给Android微信做个24小时值班机器人(附完整代码)

Android微信自动化&#xff1a;用uiautomation2打造全天候智能应答系统 深夜11点&#xff0c;你的手机突然亮起——又是一位老客户发来产品咨询。而此时&#xff0c;你开发的微信机器人已经自动识别关键词&#xff0c;秒回了详细的产品参数和购买链接。这不是科幻场景&#xff…...

Kandinsky-5.0-I2V-Lite-5s社区作品精选:看看其他开发者创造了什么

Kandinsky-5.0-I2V-Lite-5s社区作品精选&#xff1a;看看其他开发者创造了什么 1. 开篇&#xff1a;一场视觉创意的盛宴 Kandinsky-5.0-I2V-Lite-5s作为当前最热门的开源图像转视频模型&#xff0c;正在全球开发者社区掀起创作热潮。短短5秒就能将静态图片转化为富有生命力的…...

从选型到贴片:启英泰伦CI13XX芯片硬件设计避坑指南(附PCB布局建议)

启英泰伦CI13XX芯片硬件设计实战&#xff1a;从选型到量产的工程化解决方案 在智能语音硬件开发领域&#xff0c;启英泰伦CI13XX系列芯片凭借其高度集成的BNPU V3神经网络处理器和丰富的接口资源&#xff0c;已成为离线语音识别方案的热门选择。然而&#xff0c;从芯片选型到最…...

BilibiliDown:一键解锁B站视频下载新体验,你的个人视频收藏管家

BilibiliDown&#xff1a;一键解锁B站视频下载新体验&#xff0c;你的个人视频收藏管家 【免费下载链接】BilibiliDown (GUI-多平台支持) B站 哔哩哔哩 视频下载器。支持稍后再看、收藏夹、UP主视频批量下载|Bilibili Video Downloader &#x1f633; 项目地址: https://gitc…...

蓝牙键盘连接难题:如何正确输入PIN码?

1. 蓝牙键盘连接为何需要PIN码&#xff1f; 第一次用蓝牙键盘连接电脑时&#xff0c;很多朋友都会遇到这个让人抓狂的场景&#xff1a;电脑屏幕上突然弹出"请输入PIN码"的提示&#xff0c;但手边的蓝牙键盘根本没法输入数字。这种情况在Windows电脑连接苹果Magic Key…...