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

[贪心算法] 国王游戏

题目描述

​ 恰逢 H 国国庆,国王邀请 n 位大臣来玩一个有奖游戏。首先,他让每个大臣在左、右手上面分别写下一个整数,国王自己也在左、右手上各写一个整数。然后,让这 n 位大臣排成一排,国王站在队伍的最前面。排好队后,所有的大臣都会获得国王奖赏的若干金币,每位大臣获得的金币数分别是:排在该大臣前面的所有人的左手上的数的乘积除以他自己右手上的数,然后向下取整得到的结果。

​ 国王不希望某一个大臣获得特别多的奖赏,所以他想请你帮他重新安排一下队伍的顺序,使得获得奖赏最多的大臣,所获奖赏尽可能的少。注意,国王的位置始终在队伍的最前面。


输入

​ 第一行包含一个整数 n,表示大臣的人数。

​ 第二行包含两个整数 a 和 b,之间用一个空格隔开,分别表示国王左手和右手上的整数。(均小于 10000)

​ 接下来 n 行,每行包含两个整数 a 和 b,之间用一个空格隔开,分别表示每个大臣左手和右手上的整数。(均小于 10000)

输出

​ 输出一个整数,表示重新排列后的队伍中获奖赏最多的大臣所获得的金币数。


样例输入
3
1 1
2 3
7 4
4 6
样例输出
2

数据规模与约定

​ 时间限制:1 s

​ 内存限制:256 M

​ 100% 的数据保证 1≤n≤1000

解题分析

本题需要采用一种微扰的思想去探索贪心算法的实现,如何才能排队让得到最多的钱的大臣得到的钱尽可能地少呢?不妨这样去思考,我们假设这些大臣排成了C0,C1,C2,C3,......,Ci,Ci+1, .......Cn,其中C0就是国王,国王一定要排在第一位的,所以不用去考虑他。不妨假设Ci+1这个大臣得到的奖赏就是最多的,那么他得到的钱Pi+1=a0*a1*a2*.....*ai+1/bi+1,在我们的假设下,这个钱一定会大于等于其他人能够得到的钱,接下来,我们考虑对整个队列进行一个“微扰”,就是说,我们把Ci和Ci+1两个人调换一下位置,在这样的调换位置中,可以发现,整个队列中,除了Ci和Ci+1,其他所有人获得的奖赏都,没有发生任何的改变。而Ci+1得到的钱变成了a0*a1*...*ai-1*ai+1/bi+1,Ci得到的钱变成了a0*a1*.....*ai-1*ai+1*ai/bi,可以发现Ci+1得到的钱变少了而Ci得到的钱和原来相比变多了,这个时候,只需让a0*a1*.....*ai-1*ai+1*ai/bi<a0*a1*a2*.....*ai+1/bi+1,也就是ai+1*bi+1<ai*bi,那么Ci得到的钱就小于原来Ci+1得到的钱。也就是说,当ai+1*bi+1<ai*bi的时候,我们让Ci+1和Ci交换位置,这个时候这两个大臣得到的钱一定会比原来更少,换言之,如果我们让左右手相乘的数小的人排前面,大的人排后面,那么得到奖赏最多的大臣得到的钱是所有排列情况中最少的。

这段程序使用了贪心算法来解决问题。

首先,程序读取输入数据,包括大臣的人数n以及每个人的左手和右手上的整数。

然后,程序定义了一个cmp函数来作为排序比较函数。该函数比较两个大臣的获奖金币数,根据题目要求,返回较小的金币数对应的大臣排在前面。

接下来,程序通过调用sort函数对大臣进行排序,排序的依据是cmp函数的返回结果。这样就得到了一个重新排列后的队伍,使得获得奖赏最多的大臣所获得的金币数尽可能少。

然后,程序初始化maxSum为一个较小的负无穷值,p为国王左手上的整数。

接着,程序使用循环遍历重新排列后的队伍中的每个大臣。对于每个大臣,程序计算其获奖金币数并更新maxSum的值。具体的计算方法是将p除以该大臣右手上的整数,并将结果与maxSum比较,取较大值作为新的maxSum。然后,程序将p乘以该大臣左手上的整数,为下一个大臣的计算做准备。

最后,程序输出maxSum,即重新排列后的队伍中获得奖赏最多的大臣所获得的金币数。

该算法的时间复杂度为O(nlogn),其中n为大臣的人数。这是因为排序的时间复杂度为O(nlogn),而循环遍历大臣的时间复杂度为O(n)。

代码实现
#include <iostream>
#include <algorithm>
#define MAXN 10005
using namespace std;
int n,a[MAXN],b[MAXN],c[MAXN];
bool cmp(int i,int j){if(a[i]*b[i]<a[j]*b[j]){return 1;}return 0;
}
int main(){scanf("%d",&n);for(int i=0;i<=n;i++){scanf("%d %d",&a[i],&b[i]);}for(int i=0;i<=n;i++){c[i]=i;}sort(c+1,c+n+1,cmp);int maxSum=-1e9,p=1*a[0];for(int i=1;i<=n;i++){int temp=p/b[c[i]];maxSum=max(maxSum,temp);p*=a[c[i]];}printf("%d\n",maxSum);return 0;
}

相关文章:

[贪心算法] 国王游戏

题目描述 ​ 恰逢 H 国国庆,国王邀请 n 位大臣来玩一个有奖游戏。首先,他让每个大臣在左、右手上面分别写下一个整数&#xff0c;国王自己也在左、右手上各写一个整数。然后&#xff0c;让这 n 位大臣排成一排&#xff0c;国王站在队伍的最前面。排好队后&#xff0c;所有的大…...

meter报OOM错误,如何解决?

根据在之前的压测过程碰到的问题&#xff0c;今天稍微总结总结&#xff0c;以后方便自己查找。 一、单台Mac进行压测时候&#xff0c;压测客户端Jmeter启动超过2000个线程&#xff0c;Jmeter报OOM错误&#xff0c;如何解决&#xff1f; 解答&#xff1a;单台Mac配置内存为8G&…...

第二百六十九回

文章目录 概念介绍设置方法示例代码内容总结 我们在上一章回中介绍了Card Widget相关的内容&#xff0c;本章回中将介绍国际化设置.闲话休提&#xff0c;让我们一起Talk Flutter吧。 概念介绍 我们在这里说的国际化设置是指在App设置相关操作&#xff0c;这样可以让不同国家的…...

未来能源转型之路:2023年第十三届中国国际储能大会启示录

在2023年第十三届中国国际储能大会上&#xff0c;全球各地的能源专家、学者和企业代表齐聚一堂&#xff0c;共同探讨了储能技术在推动能源转型中的重要作用。对于我们普通人来说&#xff0c;从这场大会中可以学到什么呢&#xff1f; 一、储能技术是未来能源发展的关键 随着可再…...

rviz可视化机械臂(python)

一、准备的东西 一个机械臂的urdf 规划的路径点 二、launch文件的撰写 1.初始化 <?xml version"1.0" encoding"utf-8"?> <launch><param name"robot_description" textfile"机械臂.urdf" /><node name&qu…...

《设计模式的艺术》笔记 - 享元模式

介绍 享元模式运用共享技术有效地支持大量细粒度对象的复用。系统只使用少量的对象&#xff0c;而这些对象都很相似&#xff0c;状态变化很小&#xff0c;可以实现对象的多次复用。由于享元模式要求能够共享的对象必须是细粒度对象&#xff0c;因此它又称为轻量级模式&#xff…...

ubuntu系统(10):使用samba共享linux主机中文件

目录 一、samba安装步骤 1、Linux主机端操作 &#xff08;1&#xff09;安装sabma &#xff08;2&#xff09;修改samba配置文件 &#xff08;3&#xff09;为user_name用户设置samba访问的密码 &#xff08;4&#xff09;重启samba服务 2、Windows端 二、使用 1、代码…...

数据集成时表模型同步方法解析

01 背景介绍 数据治理的第一步&#xff0c;也是数据中台的一个基础功能 — 即将来自各类业务数据源的数据&#xff0c;同步集成至中台 ODS 层。业务数据源多种多样&#xff0c;单单可能涉及到的主流关系型数据库就有近十种。功能更加全面的数据中台通常还具有对接非关系型数据…...

彻底解决charles抓包https乱码的问题

最近做js逆向&#xff0c;听说charles比浏览器抓包更好用&#xff0c;结果发现全是乱码&#xff0c;根本没法用。 然后查询网上水文&#xff1a;全部都是装证书&#xff0c;根本没用&#xff01; 最后终于找到解决办法&#xff0c;在这里记录一下&#xff1a; 乱码的根本原因…...

Towards Robust Blind Face Restoration with Codebook Lookup Transformer

Towards Real World Blind Face Restoration with Generative Facial Prior 这个projec相对codeformer已经是老一些的了&#xff0c;CodeFormer paper说自己的效果比这个更好。 有看了这个视频&#xff0c;它借用了R-ESRGAN 4x 和 GFPGAN 50%&#xff0c;既保留了一些人物特征…...

flutter3使用dio库发送FormData数据格式时候的坑,和get库冲突解决办法

问题描述 问题1&#xff1a;当你使用FormData.from(Flutter3直接不能用)的时候&#xff0c;可能会提示没有这个方法&#xff0c;或者使用FormData.fromMap(flutter3的dio支持)的时候也提示没有&#xff0c;这时候可能就是和get库里面的Formdata冲突了 问题1&#xff1a;The me…...

matlab读取pwm波数据,不用timer的方法,这里可以参考。Matlab/Simulink之STM32开发-编码器测速

这里提供了一个不用timer的方法&#xff0c;可以参考&#xff1a; https://blog.csdn.net/weixin_36967309/article/details/88699830 Matlab/Simulink之STM32开发-编码器测速...

使用 Python 创造你自己的计算机游戏(游戏编程快速上手)第四版:第十九章到第二十一章

十九、碰撞检测 原文&#xff1a;inventwithpython.com/invent4thed/chapter19.html 译者&#xff1a;飞龙 协议&#xff1a;CC BY-NC-SA 4.0 碰撞检测涉及确定屏幕上的两个物体何时相互接触&#xff08;即发生碰撞&#xff09;。碰撞检测对于游戏非常有用。例如&#xff0c;如…...

Multimodal Multitask Learning with a Unified Transformer

SNLI-VE dataset&#xff0c;natural language understanding tasks&#xff1a;MNLI&#xff0c;QNLI&#xff0c;QQP&#xff0c;SST-2 截止到发文时间的issue数&#xff0c;多吓人呐&#xff0c;不建议复现...

c指针和字符数组初学者比较好的例子

本练习的主题&#xff1a;一个对象的指针可以修改这个对象的内容&#xff1b; 注&#xff1a;对象是指一个固定大小的内存块。 #define _CRT_SECURE_NO_WARNINGS #include <stdio.h> #include <string.h> #include <stdlib.h> int getMem(char **p1,int *m…...

微信原生小程序上传与识别以及监听多个checkbox事件打开pdf

1.点击上传并识别 组件样式<van-field border"{{ false }}" placeholder"请输入银行卡卡号" model:value"{{bankNo}}" label"卡号"><van-icon bindtap"handleChooseImg" slot"right-icon" name"sca…...

关于C#中Monitor的wait/pulse的理解

wait&#xff1a;表示释放对象上的锁并阻止当前线程&#xff0c;直到它重新获取该锁。 pulse&#xff1a;表示通知等待队列中的线程锁定对象状态的更改。 当线程调用 Wait 时&#xff0c;它会释放对象上的锁并进入对象的等待队列。 对象的就绪队列中的下一个线程 (如果有一个…...

LeetCode 2894. 分类求和并作差

给你两个正整数 n 和 m 。 现定义两个整数 num1 和 num2 &#xff0c;如下所示&#xff1a; num1&#xff1a;范围 [1, n] 内所有 无法被 m 整除 的整数之和。 num2&#xff1a;范围 [1, n] 内所有 能够被 m 整除 的整数之和。 返回整数 num1 - num2 。 示例 1&#xff1a; …...

PLSQL 把多个字段转为json格式

PLSQL 把多个字段转为json格式 sql Select cc.bm, cc.xm, json_arrayagg(cc.hb) jgFrom (Select aa.bm, aa.xm, json_object(aa.ksbh, aa.wjmc) hbFrom (Select 001 bm, 老六 xm, 0001 ksbh, 文具盒 wjmcFrom dual tUnion AllSelect 001 bm, 老六 xm, 0002 ksbh, 毛笔 wjmcFr…...

国内环境 GitHub 拉取仓库速度慢的缓解方案

第一步&#xff1a; 浏览器打开如下两个网址&#xff0c;找到对应 IP 地址&#xff1a; GitHub.com - GitHub: Lets build from here GitHubgithub.global.ssl.fastly.net 假设对应 IP 地址分别为 140.82.xx.xxx 和 199.232.yy.yyy 第二步&#xff1a; 编辑 hosts 文件 sud…...

使用docker在3台服务器上搭建基于redis 6.x的一主两从三台均是哨兵模式

一、环境及版本说明 如果服务器已经安装了docker,则忽略此步骤,如果没有安装,则可以按照一下方式安装: 1. 在线安装(有互联网环境): 请看我这篇文章 传送阵>> 点我查看 2. 离线安装(内网环境):请看我这篇文章 传送阵>> 点我查看 说明&#xff1a;假设每台服务器已…...

java_网络服务相关_gateway_nacos_feign区别联系

1. spring-cloud-starter-gateway 作用&#xff1a;作为微服务架构的网关&#xff0c;统一入口&#xff0c;处理所有外部请求。 核心能力&#xff1a; 路由转发&#xff08;基于路径、服务名等&#xff09;过滤器&#xff08;鉴权、限流、日志、Header 处理&#xff09;支持负…...

基于FPGA的PID算法学习———实现PID比例控制算法

基于FPGA的PID算法学习 前言一、PID算法分析二、PID仿真分析1. PID代码2.PI代码3.P代码4.顶层5.测试文件6.仿真波形 总结 前言 学习内容&#xff1a;参考网站&#xff1a; PID算法控制 PID即&#xff1a;Proportional&#xff08;比例&#xff09;、Integral&#xff08;积分&…...

从WWDC看苹果产品发展的规律

WWDC 是苹果公司一年一度面向全球开发者的盛会&#xff0c;其主题演讲展现了苹果在产品设计、技术路线、用户体验和生态系统构建上的核心理念与演进脉络。我们借助 ChatGPT Deep Research 工具&#xff0c;对过去十年 WWDC 主题演讲内容进行了系统化分析&#xff0c;形成了这份…...

在rocky linux 9.5上在线安装 docker

前面是指南&#xff0c;后面是日志 sudo dnf config-manager --add-repo https://download.docker.com/linux/centos/docker-ce.repo sudo dnf install docker-ce docker-ce-cli containerd.io -y docker version sudo systemctl start docker sudo systemctl status docker …...

Qt Http Server模块功能及架构

Qt Http Server 是 Qt 6.0 中引入的一个新模块&#xff0c;它提供了一个轻量级的 HTTP 服务器实现&#xff0c;主要用于构建基于 HTTP 的应用程序和服务。 功能介绍&#xff1a; 主要功能 HTTP服务器功能&#xff1a; 支持 HTTP/1.1 协议 简单的请求/响应处理模型 支持 GET…...

高危文件识别的常用算法:原理、应用与企业场景

高危文件识别的常用算法&#xff1a;原理、应用与企业场景 高危文件识别旨在检测可能导致安全威胁的文件&#xff0c;如包含恶意代码、敏感数据或欺诈内容的文档&#xff0c;在企业协同办公环境中&#xff08;如Teams、Google Workspace&#xff09;尤为重要。结合大模型技术&…...

令牌桶 滑动窗口->限流 分布式信号量->限并发的原理 lua脚本分析介绍

文章目录 前言限流限制并发的实际理解限流令牌桶代码实现结果分析令牌桶lua的模拟实现原理总结&#xff1a; 滑动窗口代码实现结果分析lua脚本原理解析 限并发分布式信号量代码实现结果分析lua脚本实现原理 双注解去实现限流 并发结果分析&#xff1a; 实际业务去理解体会统一注…...

UR 协作机器人「三剑客」:精密轻量担当(UR7e)、全能协作主力(UR12e)、重型任务专家(UR15)

UR协作机器人正以其卓越性能在现代制造业自动化中扮演重要角色。UR7e、UR12e和UR15通过创新技术和精准设计满足了不同行业的多样化需求。其中&#xff0c;UR15以其速度、精度及人工智能准备能力成为自动化领域的重要突破。UR7e和UR12e则在负载规格和市场定位上不断优化&#xf…...

css3笔记 (1) 自用

outline: none 用于移除元素获得焦点时默认的轮廓线 broder:0 用于移除边框 font-size&#xff1a;0 用于设置字体不显示 list-style: none 消除<li> 标签默认样式 margin: xx auto 版心居中 width:100% 通栏 vertical-align 作用于行内元素 / 表格单元格&#xff…...