算法篇:贪心算法

server/2024/11/29 4:51:37/

题目一:均分纸牌

有n堆纸牌,编号分别为 1,2,…,n1,2,…,n。每堆上有若干张,但纸牌总数必为nn的倍数。可以在任一堆上取若干张纸牌,然后移动。

移牌规则为:在编号为11的堆上取的纸牌,只能移到编号为 22 的堆上;在编号为 nn 的堆上取的纸牌,只能移到编号为n−1n−1的堆上;其他堆上取的纸牌,可以移到相邻左边或右边的堆上。

现在要求找出一种移动方法,用最少的移动次数使每堆上纸牌数都一样多。

例如:

n=4堆纸牌数分别为:  ① 9 ② 8 ③ 17 ④ 6

移动3次可达到目的:

从 ③ 取4张牌放到④(9 8 13 10)->从③取3张牌放到 ②(9 11 10 10)-> 从②取1张牌放到①(10 10 10 10)。

cards = [9,8,17,6,9,11]def min_moves_to_balance():n = len(cards)target = sum(cards) // n  # 每堆纸牌应达到的目标数量moves = 0  # 记录移动次数queue = [(i, cards[i] - target) for i in range(n) if cards[i] != target]  # 创建一个队列来存储不平衡的堆及其差值print(queue)while queue:# 从队列中取出一个不平衡的堆i, diff = queue.pop(0)# 根据堆的编号来决定如何移动纸牌if i == 0:# 如果是第一堆,并且纸牌多于目标数量,则只能向第二堆移动if diff > 0:move_amount = min(diff, target - cards[1])cards[0] -= move_amountcards[1] += move_amountmoves += 1  # 注意:这里应该按移动的次数累加,而不是按移动的量# 更新第二堆的状态,如果第二堆仍然不平衡,则重新加入队列if cards[1] != target:queue.append((1, cards[1] - target))elif i == n - 1:# 如果是最后一堆,并且纸牌多于目标数量,则只能向倒数第二堆移动if diff > 0:move_amount = min(diff, target - cards[n - 2])cards[n - 1] -= move_amountcards[n - 2] += move_amountmoves += 1# 更新倒数第二堆的状态,如果仍然不平衡,则重新加入队列if cards[n - 2] != target:queue.append((n - 2, cards[n - 2] - target))else:# 如果是中间的堆,则可以向左边或右边移动纸牌if diff > 0:# 尝试向右边移动move_right = min(diff, target - cards[i + 1])if move_right > 0:cards[i] -= move_rightcards[i + 1] += move_rightmoves += 1# 更新右边堆的状态,如果仍然不平衡,则重新加入队列if cards[i + 1] != target:queue.append((i + 1, cards[i + 1] - target))# 如果右边堆已满或无法再接收更多纸牌,则尝试向左边移动move_left = diff - move_rightif move_left > 0:cards[i] -= move_leftcards[i - 1] += move_leftmoves += 1# 更新左边堆的状态,如果仍然不平衡,则重新加入队列if cards[i - 1] != target:queue.append((i - 1, cards[i - 1] - target))elif diff < 0:# 如果纸牌少于目标数量,则尝试从左边或右边接收纸牌# 注意:这里我们不需要显式地处理从左边或右边接收纸牌的情况,# 因为在之前的迭代中,相邻的堆已经(或将会)尝试向我们当前处理的堆移动纸牌。# 我们只需要确保在之前的迭代中,相邻堆有多余的纸牌可以移动给我们。# 因此,这里的diff < 0情况实际上会被之前的迭代处理掉(通过相邻堆的diff > 0情况)。pass  # 不需要执行任何操作,因为相邻堆会负责平衡我们# 由于我们按移动的次数累加,而不是按移动的量,所以moves直接就是最少的移动次数return moves# 示例测试ret = min_moves_to_balance() # 输出应为符合题目要求的最少移动次数print(ret)# 为了验证结果,可以打印最终平衡的纸牌堆(理论上应该是[10, 10, 10, 10])
print(cards)


http://www.ppmy.cn/server/145816.html

相关文章

读书笔记_《创华为.任正非传》_精华书摘

人生经历 43岁&#xff0c;开始创建华为 爷爷:金华火腿乡间厨师 父亲: 1910年生&#xff0c;北平民大经济系读书->职业学校任教->国民党兵工厂会计&#xff0c;组织读书会(读书会后来有很多人在新中国成立后成为高级干部。) 母亲: 高中毕业&#xff0c;乡村教师&#xf…

MacBook上安装 Windows 10 后,System 进程 CPU 占用 100% 的问题

在 MacBook 2014 上安装 Windows 10 后&#xff0c;System 进程 CPU 占用 100% 的问题通常与以下因素有关&#xff1a; 1. 驱动程序问题 在 Mac 上运行 Windows 通常需要通过 Boot Camp 提供正确的驱动程序。不兼容或缺失的驱动可能导致 CPU 高占用。 解决方法 检查驱动程序是…

14、保存与加载PyTorch训练的模型和超参数

文章目录 1. state_dict2. 模型保存3. check_point4. 详细保存5. Docker6. 机器学习常用库 1. state_dict nn.Module 类是所有神经网络构建的基类&#xff0c;即自己构建一个深度神经网络也是需要继承自nn.Module类才行&#xff0c;并且nn.Module中的state_dict包含神经网络中…

【杂谈】-Linux中的GUI与图形栈

Linux中的GUI与图形栈 在本文中&#xff0c;我们将探讨基于Linux操作系统中使用的图形栈。我们将了解使图形应用程序成为可能的不同技术&#xff0c;以及它们是如何相互交互的。我们将从基础开始&#xff0c;逐步引导至高级的GUI工具包。 最后&#xff0c;我们将讨论这些技术…

使用 Go 语言封装 MinIO 相关操作

目录 使用 Go 语言封装 MinIO 相关操作背景介绍代码实现结构体定义初始化 MinIO 客户端上传文件下载文件列出文件删除文件获取文件的预签名 URL 使用示例总结 使用 Go 语言封装 MinIO 相关操作 背景介绍 MinIO 是一个高性能的对象存储服务&#xff0c;兼容 Amazon S3 API&…

鸿蒙进阶篇-状态管理之@Prop@Link

大家好啊&#xff0c;这里是鸿蒙开天组&#xff0c;今天我们来学习状态管理。 开始组件化开发之后&#xff0c;如何管理组件的状态会变得尤为重要&#xff0c;咱们接下来系统的学习一下这部分的内容 状态管理机制 在声明式UI编程框架中&#xff0c;UI是程序状态的运行结果&a…

【网络安全】

黑客入侵 什么是黑客入侵&#xff1f; “黑客”是一个外来词&#xff0c;是英语单词hacker的中文音译。最初&#xff0c;“黑客”只是一个褒义词&#xff0c;指的是那些尽力挖掘计算机程序最大潜力的点脑精英&#xff0c;他们讨论软件黑客的技巧和态度&#xff0c;以及共享文化…

【C++】类(三):类的其它特性

7.3 类的其它特性 本节将继续介绍之前章节当中 Sales_data 没有体现出来的类的特性&#xff0c;包括&#xff1a;类型成员、类的成员的类内初始值、可变数据成员、内联成员函数、从成员函数返回*this、如何定义并使用类类型及友元类等。 7.3.1 类成员再探 这部分定义了一对相…