贪心算法——排队打水问题

2023-11-13

*/6.3 排队打水问题:有n个人排队到r个水龙头去打水,他们装满水桶的时间为t1,t2,…,tn为正整数且个不相等。
应如何安排他们打水顺序才能使他们花费的时间最少。
算法分析:时间总和=等待时间+装水时间。采用贪心思想。先sort(),默认将装水时间从小到大排序。
n个人,r个水龙头,可以以水龙头为序将队伍序分割成n/r个小组,每小组的成员分别对应r个位置。
实际上就是将人依序分成r个小队打水。比如有三个水龙头,分成三个小队,1、4、7… ,2、5、8…,3、6、9…
可以验证是否符合贪心:从序号第1的人开始依次往后选择水龙头,为了等待时间+灌水时间最小是不是该这样站队?
在这里插入图片描述
*/
#include<stdio.h>
#include
#include //C++标准模板库STL,用到sort排序
using namespace std;

int main()
{

int a[1000],b[1000],n,r; //a数组存放每个人的装水时间,b数组存放每个人的总时间(等待时间+打水时间) 
memset(a,0,sizeof(a));  //数组初始化为0 
memset(b,
本文内容由网友自发贡献,版权归原作者所有,本站不承担相应法律责任。如您发现有涉嫌抄袭侵权的内容,请联系:hwhale#tublm.com(使用前将#替换为@)

贪心算法——排队打水问题 的相关文章

  • 归并排序,自顶向下,自底向上

    http blog csdn net cjf iceking article details 7920153
  • 二分法总结

    findN 寻找某个数在递增序列里 找不到返回 1 def findN nums n i 0 j len nums 1 while i lt j middle i j i 2 if nums middle n return True ret
  • # 洗牌算法

    基本概念 等概率将将一个数组N打乱 概率每次都是1 N 加上 方法一 全局洗牌 从 0到N 1的数组下标 每次随机产生两个0到 N 1之间的数 进行交换 void get rand number int array int length i
  • 动态规划算法的优化技巧

    关键词 动态规划 时间复杂度 优化 状态 摘要 动态规划是信息学竞赛中一种常用的程序设计方法 本文着重讨论了运用动态规划思想解题时时间效率的优化 全文分为四个部分 首先讨论了动态规划时间效率优化的可行性和必要性 接着给出了动态规划时间复杂度
  • 【NOIP 2004 提高组】合并果子

    题就自己找啦 各大OJ上应该都有 题目 题目描述 在一个果园里 多多已经将所有的果子打了下来 而且按果子的不同种类分成了不同的堆 多多决定把所有的果子合成一堆 每一次合并 多多可以把两堆果子合并到一起 消耗的体力等于两堆果子的重量之和 可以
  • 一致性hash算法 - consistent hashing

    一致性hash算法 consistent hashing consistent hashing 算法早在 1997 年就在论文 Consistent hashing and random trees 中被提出 目前在 cache 系统中应用
  • 程序员面试题精选100题(40)-扑克牌的顺子

    程序员面试题精选100题 40 扑克牌的顺子 题目 从扑克牌中随机抽5张牌 判断是不是一个顺子 即这5张牌是不是连续的 2 10为数字本身 A为1 J为11 Q为12 K为13 而大小王可以看成任意数字 分析 这题目很有意思 是一个典型的寓
  • 蓝桥题解(不定期更新)

    597 跑步锻炼 import math if name main moth 0 31 28 31 30 31 30 31 31 30 31 30 31 day 6 ans 0 for year in range 2000 2021 if
  • 程序员面试题精选100题(04)-二元树中和为某一值的所有路径

    程序员面试题精选100题 04 二元树中和为某一值的所有路径 题目 输入一个整数和一棵二元树 从树的根结点开始往下访问一直到叶结点所经过的所有结点形成一条路径 打印出和与输入整数相等的所有路径 例如输入整数22和如下二元树 10 5 12
  • 【数学基础】 线性代数以及符号编总

    1基本概念和符号 线性代数可以对一组线性方程进行简洁地表示和运算 例如 对于这个方程组 这里有两个方程和两个变量 如果你学过高中代数的话 你肯定知道 可以为x1 和x2找到一组唯一的解 除非方程可以进一步简化 例如 如果第二个方程只是第一个
  • 程序员面试题精选100题(31)-从尾到头输出链表

    程序员面试题精选100题 31 从尾到头输出链表 题目 输入一个链表的头结点 从尾到头反过来输出每个结点的值 链表结点定义如下 struct ListNode int m nKey ListNode m pNext 方法一 看到这道题后 第
  • 程序员面试题精选100题(48)-二叉树两结点的最低共同父结点

    程序员面试题精选100题 48 二叉树两结点的最低共同父结点 题目 二叉树的结点定义如下 struct TreeNode int m nvalue TreeNode m pLeft TreeNode m pRight 输入二叉树中的两个结点
  • c++二分查找—来自编程珠玑

    c 二分查找 来自编程珠玑 二分查找法 Binary search algorithm 是一个很常见的算法 从 编程珠玑 里再次看到时又有新的收获 直接看代码吧 下面是常见的实现代码 int binary search int a int
  • opencv CvSolve函数深度解析

    Opencv CvSolve函数主要是用来求解线性系统Ax b的方程 X的解 solve函数跟它的算法是一样的 也是用来求解线性系统 设方程Ax b 根据有效的方程个数和未知数的个数 可以分为以下3种情况 1 rank A lt n 也就是
  • 深度优先搜索——搜索与回溯,从n个数中取出r个数的排列

    5 2 1 include
  • 贪心算法——排队打水问题

    6 3 排队打水问题 有n个人排队到r个水龙头去打水 他们装满水桶的时间为t1 t2 tn为正整数且个不相等 应如何安排他们打水顺序才能使他们花费的时间最少 算法分析 时间总和 等待时间 装水时间 采用贪心思想 先sort 默认将装水时间从
  • 二分查找及二分答案

    一 二分思想 二分是一种常用且非常精妙的算法 常常是我们解答问题的突破口 二分的基本用途是在单调序列或单调函数中做查找操作 因此当问题的答案具有单调性时 就可以通过二分把求解转化为判定 根据复杂度理论 可知判定的难度小于求解 这使得二分的应
  • 程序员面试题精选100题(30)-赋值运算符重载函数[C/C++/C#]

    程序员面试题精选100题 30 赋值运算符重载函数 C C C 问题 给出如下CMyString的声明 要求为该类型添加赋值运算符函数 class CMyString public CMyString char pData NULL CMy
  • KMP算法是怎么被设计出来的

    定义 我们假设要在主串中寻找子串出现的所有位置 我们记主串中的开始位置为匹配位置 如在 abc 中匹配 bc 则匹配位置为 2 暴力 我们把匹配过程拆解为 枚举匹配位置 验证主串从匹配位置开始是否一一匹配子串 以此 有显然的 O n m
  • 前缀和与差分(分析与模板)

    前缀和 处理数组公式 s i s i 1 num i 输出区间和公式 s r s l 1 模板 include

随机推荐

  • 虚拟机打开防火墙端口相关指令

    本篇文章用于记录在虚拟机操作过程中对于查看防火墙状态 开启防火墙 关闭防火墙指令进行记录 查看防火墙状态 systemctl status firewalld 开启防火墙 systemctl start firewalld 关闭防火墙 sy
  • 40 个 常用的 SpringBoot 注解,你知道几个?

    一 Spring Web MVC 与 Spring Bean 注解 Spring Web MVC 注解 RequestMapping RequestMapping注解的主要用途是将Web请求与请求处理类中的方法进行映射 Spring MVC
  • eNSP——VLAN配置实验

    目录 一 新建拓扑 二 配置LSW5 三 配置LSW6 一 新建拓扑 实现效果 PC10可以ping通PC12 ping不通PC11 PC13 二 配置LSW5 1 系统视图开启VLAN100 2 进入接口G0 0 1配置VLAN acce
  • signature=b05c505286f606b32d69ab58ee3e7bf4,reduce-css-calc/yarn.lock at 0f6c532cf9dc52ac3cb23e143eaf...

    THIS IS AN AUTOGENERATED FILE DO NOT EDIT THIS FILE DIRECTLY yarn lockfile v1 ava babel preset stage 4 1 0 0 version 1 1
  • 云计算之你必须知道的几个会议和杂志

    云计算现在被大家炒的热火朝天 那么很多人也想更多了解云计算 那么我就给大家介绍几个杂志和网站 IEEE International Conference on Cloud Computing http www thecloudcomputi
  • vue中的promise对象,async和await学习记录

    promise有待学习 先记录一下最近再项目中学的关于async和await async await 其实就是用同步的写法去实现异步方法 async deleteproduct record const result await produ
  • npm 配置淘宝镜像

    首先解释一下 npm 为什么要配置淘宝镜像 原因 因为node js 默认使用的是国外的网站 国内访问有一个跨国内局域网的操作 所以就会有时候很慢 这就跟为什么网站的静态资源有些会使用CDN 加速一样的 淘宝镜像是什么 就是npm 很多的插
  • hive转义问题详解

    hive转义问题详解 引言 hive控制台执行 字符串不包含 字符串包含 hive e的方式嵌入到shell脚本执行 字符串不包含 字符串包含 总结 引言 hive转义问题想必进来的同学都遇到过 这里就直奔主题了 此类问题大致可以分为两种常
  • Linux上快速安装软RAID详细步骤

    常见问题服务平台 2018 11 17 物理环境 虚拟机CentOS6 4 配置 8G内存 2 2核cpu 3块虚拟硬盘 sda sdb sdc sdb和sdc是完全一样的 在实际生产环境中 系统硬盘与数据库和应用是分开的 这样有利于系统的
  • HDRP

    HDRP 的 10 版本支持 Unity 2020 LTS 及以上 新版的 HDRP 软件包将继续优化用户友好的界面 灵活的功能 管线的稳定性和总体性能 但如果想将 HDRP 设置到最佳状态 你必须要了解所有主要的管线设置 及其背后的原理和
  • Oracle报错:IO Error: The Network Adapter could not establish the connection

    Caused by oracle net ns NetException The Network Adapter could not establish the connection at oracle net nt ConnStrateg
  • 深度学习框架Pytorch快速开发与实践

    决定用两个星期读完这本书 并自己用Pytorch搭建一个模型 2019 8 5 第一章深度学习介绍 明确学习目标 深度学习难点不是深度学习本身 难的是你要吃透问题 如何用深度学习的逻辑去思考你自己的问题 有针对性地设计模型 难的是你有分析问
  • 机器学习系列(7)_机器学习路线图(附资料)

    作者 龙心尘 寒小阳 时间 2016年2月 出处 http blog csdn net longxinchen ml article details 50749614 http blog csdn net han xiaoyang arti
  • epoll高度封装reactor,几乎所有可见服务器的底层框架

    目录 前言 reactor是什么 如何理解 reactor所需组件流程分析 组件 流程 如何将epoll的IO驱动封装成reactor事件反应堆驱动 reactor分块分析实现 注册事件处理器部分流程 多路复用器监视多路IO事件 事件分发器
  • 【React学习】React更新渲染原理

    当我们调用 setState 之后发生了什么 react经历了怎样的过程将新的 state 渲染到页面上 一次react更新 核心就是对虚拟dom进行diff 找出最少的需要变化的dom节点 然后对其进行相应的dom操作 用户即可在页面上看
  • MySQL数据导入--load data

    起因 朋友的数据库 用的版本是5 5 19 服务端和客户端字符集都是utf8 因为某些原因 系统经过好多人的开发和处理 同一个表存在多种字符集写入 so乱码问题 时有发生 为了彻底解决这个问题 我这边的操作如下 1 核查工程中转码的地方 2
  • Python初学者的一个常见错误

    大家都知道 列表是可变数据类型 而可变数据类型的操作尤其需要我们细心 不然很容易出错 来看看这个例子 list1 1 2 3 4 5 list2 list1 3 print list2 list1 2 b list2 1 1 a print
  • [从零开始学DeepFaceLab-8]: 使用-命令行八大操作步骤-第5步:从源图片中提取所需图片

    目录 总体流程 步骤5 从源视频中提取图片 5 1 命令 5 data dst faceset extract manual fix bat 不推荐使用
  • vue回车事件

    一 需求 需求 登录页面在输入密码后 按回车键 Enter 触发登录 二 实现 部分代码 重点事件 keyup enter native 指的是回车监听事件 举例 keyup enter native submitForm ruleForm
  • 贪心算法——排队打水问题

    6 3 排队打水问题 有n个人排队到r个水龙头去打水 他们装满水桶的时间为t1 t2 tn为正整数且个不相等 应如何安排他们打水顺序才能使他们花费的时间最少 算法分析 时间总和 等待时间 装水时间 采用贪心思想 先sort 默认将装水时间从