渡河问题(贪心)

2024-03-18 16:20
文章标签 问题 贪心 渡河

本文主要是介绍渡河问题(贪心),希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

现在有一群人,到了一条河旁边,想要过河,但船只有一条,一次最多能载两个人,开到了对面还需要一个人负责把船开回来,而且若多人坐船,速度还是由慢的一个决定,现在求如何分配坐船,使总时间最短。

输入

输入t组数据,每组数据第1行输入n,第2行输入n个数,表示每个人过河的时间。

输出

输出t行数据,每行1个数,表示每组过河最少时间。

样例输入

1

4

1 2 5 10

样例输出

17

#include<iostream>
#include<algorithm>
using namespace std;
int time(int a[],int left){//left河岸左边的人数 int ans=0;while(left>0){if(left==1){ ans+=a[1];return ans;}else if(left==2){ans+=a[2];return ans;}else if(left==3){ans+=a[1]+a[2]+a[3];return ans;}else{//进入后else后,最慢的2人过河,且船在河岸的左边 //策略1:最快的带最慢的——1,left过河,a[left]。1返回,a[1]。1,left-1过河,a[left-1]。1返回,a[1]。 int time1=2*a[1]+a[left-1]+a[left];//策略2:最快的带次之,最慢的和次之——1,2过河,a[2]。1返回,a[1]。left,left-1过河,a[left]。a[2]返回,a[2]。 int time2=a[1]+2*a[2]+a[left];ans+=min(time1,time2);left-=2;}} 
}
int main(){int t;cin>>t;while(t--){int n;cin>>n;int a[n+1];for(int i=1;i<=n;i++){cin>>a[i];}sort(a+1,a+n+1);//将渡河时间排序cout<<time(a,n)<<endl; }return 0;
} 

 

这篇关于渡河问题(贪心)的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!


原文地址:
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:http://www.chinasem.cn/article/822916

相关文章

mybatis和mybatis-plus设置值为null不起作用问题及解决

《mybatis和mybatis-plus设置值为null不起作用问题及解决》Mybatis-Plus的FieldStrategy主要用于控制新增、更新和查询时对空值的处理策略,通过配置不同的策略类型... 目录MyBATis-plusFieldStrategy作用FieldStrategy类型每种策略的作

linux下多个硬盘划分到同一挂载点问题

《linux下多个硬盘划分到同一挂载点问题》在Linux系统中,将多个硬盘划分到同一挂载点需要通过逻辑卷管理(LVM)来实现,首先,需要将物理存储设备(如硬盘分区)创建为物理卷,然后,将这些物理卷组成... 目录linux下多个硬盘划分到同一挂载点需要明确的几个概念硬盘插上默认的是非lvm总结Linux下多

Python Jupyter Notebook导包报错问题及解决

《PythonJupyterNotebook导包报错问题及解决》在conda环境中安装包后,JupyterNotebook导入时出现ImportError,可能是由于包版本不对应或版本太高,解决方... 目录问题解决方法重新安装Jupyter NoteBook 更改Kernel总结问题在conda上安装了

pip install jupyterlab失败的原因问题及探索

《pipinstalljupyterlab失败的原因问题及探索》在学习Yolo模型时,尝试安装JupyterLab但遇到错误,错误提示缺少Rust和Cargo编译环境,因为pywinpty包需要它... 目录背景问题解决方案总结背景最近在学习Yolo模型,然后其中要下载jupyter(有点LSVmu像一个

解决jupyterLab打开后出现Config option `template_path`not recognized by `ExporterCollapsibleHeadings`问题

《解决jupyterLab打开后出现Configoption`template_path`notrecognizedby`ExporterCollapsibleHeadings`问题》在Ju... 目录jupyterLab打开后出现“templandroidate_path”相关问题这是 tensorflo

如何解决Pycharm编辑内容时有光标的问题

《如何解决Pycharm编辑内容时有光标的问题》文章介绍了如何在PyCharm中配置VimEmulator插件,包括检查插件是否已安装、下载插件以及安装IdeaVim插件的步骤... 目录Pycharm编辑内容时有光标1.如果Vim Emulator前面有对勾2.www.chinasem.cn如果tools工

最长公共子序列问题的深度分析与Java实现方式

《最长公共子序列问题的深度分析与Java实现方式》本文详细介绍了最长公共子序列(LCS)问题,包括其概念、暴力解法、动态规划解法,并提供了Java代码实现,暴力解法虽然简单,但在大数据处理中效率较低,... 目录最长公共子序列问题概述问题理解与示例分析暴力解法思路与示例代码动态规划解法DP 表的构建与意义动

Java多线程父线程向子线程传值问题及解决

《Java多线程父线程向子线程传值问题及解决》文章总结了5种解决父子之间数据传递困扰的解决方案,包括ThreadLocal+TaskDecorator、UserUtils、CustomTaskDeco... 目录1 背景2 ThreadLocal+TaskDecorator3 RequestContextH

关于Spring @Bean 相同加载顺序不同结果不同的问题记录

《关于Spring@Bean相同加载顺序不同结果不同的问题记录》本文主要探讨了在Spring5.1.3.RELEASE版本下,当有两个全注解类定义相同类型的Bean时,由于加载顺序不同,最终生成的... 目录问题说明测试输出1测试输出2@Bean注解的BeanDefiChina编程nition加入时机总结问题说明

关于最长递增子序列问题概述

《关于最长递增子序列问题概述》本文详细介绍了最长递增子序列问题的定义及两种优化解法:贪心+二分查找和动态规划+状态压缩,贪心+二分查找时间复杂度为O(nlogn),通过维护一个有序的“尾巴”数组来高效... 一、最长递增子序列问题概述1. 问题定义给定一个整数序列,例如 nums = [10, 9, 2