算法篇:贪心算法

ops/2024/11/29 0:56:19/

题目一:均分纸牌

有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/ops/137520.html

相关文章

Kafka日志索引详解以及生产常见问题分析与总结

文章目录 一、Kafka的Log日志梳理1.1、Topic下的消息如何存储1.1.1、log文件追加记录所有消息1.1.2、index和timeindex加速读取log消息日志 1.2、文件清理机制1.2.1、如何判断哪些日志文件过期了1.2.2、过期的日志文件如何处理 1.3、Kafka的文件高效读写机制1.3.1、Kafka的文件…

CBK7运营安全

1 运营部门的角色 ​ prudent man、due care&#xff08;按要求执行&#xff09;VS due diligence&#xff08;承担管理者责任&#xff09; ​ 应尽关注&#xff1a;执行了负责任的动作降低了风险。 ​ 应尽职责&#xff1a;采取了所有必要的安全步骤以了解公司或个人的实际风…

2024年11月27日Github流行趋势

项目名称&#xff1a;screenshot-to-code 项目维护者&#xff1a;abi clean99 sweep-ai kachbit vagusX项目介绍&#xff1a;通过上传截图将其转换为整洁的代码&#xff08;支持HTML/Tailwind/React/Vue&#xff09;。项目star数&#xff1a;62,429项目fork数&#xff1a;7,614…

Spring Boot 的 WebClient 实践教程

什么是 WebClient&#xff1f; 在 Spring Boot 中&#xff0c;WebClient 是 Spring WebFlux 提供的一个非阻塞、响应式的 HTTP 客户端&#xff0c;用于与 RESTful 服务或其他 HTTP 服务交互。相比于传统的 RestTemplate&#xff0c;WebClient 更加现代化&#xff0c;具有异步和…

selinux和防火墙

一、selinux的说明 SELinux 是 Security-Enhanced Linux 的缩写&#xff0c;意思是安全强化的 linux 。 SELinux 主要由美国国家安全局&#xff08; NSA &#xff09;开发&#xff0c;当初开发的目的是为了避免资源的误用。 系统资源都是通过程序进行访问的&#xff0c;如果…

C++ 内存布局与字节序详解:类大小、结构体对齐、大小端与字节序转换

文章目录 一、如何计算一个类的大小&#xff1f;二、sizeof 计算的几个关键因素&#xff1a;2.1 特殊情况&#xff08;空类、静态成员变量&#xff09;&#xff1a;2.2 示例 三、结构体对齐3.1 alignas 关键字&#xff1a;3.2 C 结构体对齐举例3.3 offsetof 宏3.3.1 如何理解偏…

界面控件Kendo UI for Angular中文教程:如何构建带图表的仪表板?(二)

Kendo UI for Angular ListView可以轻松地为客户端设置一个带有图表列表的仪表板&#xff0c;包括分页、按钮选项、数字或滚动&#xff0c;以及在没有更多项目要显示时的通知等。Kendo UI for Angular是专用于Angular开发的专业级Angular组件。telerik致力于提供纯粹的高性能An…

C++编程库与框架实战——sqlite3数据库

一,SQLite数据库简介 SQLite是可以实现类似于关系型数据库中各种操作的事务性SQL数据库引擎。 SQLite可以为应用程序提供存储于本地的嵌入式数据库,帮助应用程序实现轻量级的数据存储。 SQLite是一个库文件,并不是单独的进程,它可以静态或动态链接到C++应用程序中,然后…