[贪心算法] 国王游戏

这篇具有很好参考价值的文章主要介绍了[贪心算法] 国王游戏。希望对大家有所帮助。如果存在错误或未考虑完全的地方,请大家不吝赐教,您也可以点击"举报违法"按钮提交疑问。

题目描述

​ 恰逢 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)。文章来源地址https://www.toymoban.com/news/detail-802257.html

代码实现
#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;
}

到了这里,关于[贪心算法] 国王游戏的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处: 如若内容造成侵权/违法违规/事实不符,请点击违法举报进行投诉反馈,一经查实,立即删除!

领支付宝红包 赞助服务器费用

相关文章

  • 贪心算法-01:跳跃游戏

    贪心算法是动态规划的一个特例,相对于动态规划,使用贪心算法需要满足更多条件,但是效率比动态规划要高。 贪心选择的性质就是:每一步都做出一个局部最优解,最终的结果就是全局最优。不过这是一种特殊性质,只有一部分问题拥有这个性质。 比如面前放有100张人

    2024年01月22日
    浏览(43)
  • 贪心算法-跳跃游戏

    给你一个非负整数数组  nums  ,你最初位于数组的  第一个下标  。数组中的每个元素代表你在该位置可以跳跃的最大长度。 判断你是否能够到达最后一个下标,如果可以,返回  true  ;否则,返回  false  。 示例 1: 示例 2: 提示: 1 = nums.length = 104 0 = nums[i] = 105 贪心在

    2024年04月27日
    浏览(35)
  • DAY37:贪心算法(四)跳跃游戏+跳跃游戏Ⅱ

    给定一个非负整数数组 nums ,你最初位于数组的 第一个下标 。 数组中的每个元素代表你在该位置可以跳跃的最大长度。 判断你是否能够到达最后一个下标。 示例 1: 示例 2: 提示: 1 = nums.length = 3 * 104 0 = nums[i] = 105 思路 游戏大致规则如下图。每一步代表着能跳跃的最大长

    2024年02月12日
    浏览(44)
  • 贪心算法-跳跃游戏问题(java)

    1.1 题目描述 输入是一个非负整数数组nums,数组元素nums[i]代表你站的位置i最多能够向前跳几步。现在你站的第一个位置nums[0],请问能否跳到最后一个位置。 举例: nums = [2,3,1,1,4] 这个就可以跳到最后,返回true nums = [3,2,1,0,4]这个就无法跳到最后,返回false 1.2解题思路: 我们每

    2024年02月05日
    浏览(49)
  • 【贪心算法】Leetcode 55. 跳跃游戏【中等】

    给你一个非负整数数组 nums ,你最初位于数组的 第一个下标 。数组中的每个元素代表你在该位置可以跳跃的最大长度。 判断你是否能够到达最后一个下标,如果可以,返回 true ;否则,返回 false 。 示例 1: 输入 :nums = [2,3,1,1,4] 输出: true 解释 :可以先跳 1 步,从下标

    2024年04月28日
    浏览(52)
  • 算法 贪心2 || 122.买卖股票的最佳时机II 55. 跳跃游戏 45.跳跃游戏II

    如果想到其实 最终利润是可以分解的 ,那么本题就很容易了! 如何分解呢? 假如第0天买入,第3天卖出,那么利润为:prices[3] - prices[0]。 相当于(prices[3] - prices[2]) + (prices[2] - prices[1]) + (prices[1] - prices[0])。 此时就是把利润分解为每天为单位的维度,而不是从0天到第3天整体去

    2023年04月13日
    浏览(46)
  • 【经典LeetCode算法题目专栏分类】【第5期】贪心算法:分发饼干、跳跃游戏、模拟行走机器人

    《博主简介》 小伙伴们好,我是阿旭。专注于人工智能AI、python、计算机视觉相关分享研究。 ✌ 更多学习资源,可关注公-仲-hao:【阿旭算法与机器学习】,共同学习交流~ 👍 感谢小伙伴 们点赞、关注! class   Solution :      def   findContentChildren ( self ,  g :  List [ int ],  s

    2024年02月04日
    浏览(53)
  • Day32 贪心算法 part02 122. 买卖股票的最佳时机 II 55. 跳跃游戏 45. 跳跃游戏 II

    思路:计算每天的利润,利润如果为正,加到结果中去

    2024年01月19日
    浏览(44)
  • 【课设】java:迷宫小游戏(递归与分治、动态规划、贪心算法、回溯法、分支限界法)

    鱼弦:CSDN内容合伙人、CSDN新星导师、全栈领域优质创作者 、51CTO(Top红人+专家博主) 、github开源爱好者(go-zero源码二次开发、游戏后端架构 https://github.com/Peakchen) 递归与分治算法 原理: 递归与分治算法将问题分解为子问题,递归地解决每个子问题,最后将结果合并得到整

    2024年02月02日
    浏览(39)
  • 257.【华为OD机试真题】幼儿园篮球游戏(贪心算法-Java&Python&C++&JS实现)

    🚀点击这里可直接跳转到本专栏,可查阅顶置最新的华为OD机试宝典~ 本专栏所有题目均包含优质解题思路,高质量解题代码(JavaPythonC++JS分别实现),详细代码讲解,助你深入学习,深度掌握!

    2024年02月19日
    浏览(49)

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

请作者喝杯咖啡吧~博客赞助

支付宝扫一扫领取红包,优惠每天领

二维码1

领取红包

二维码2

领红包