🔹 题目1:最大系统内存容量
🧩 问题描述:
Amazon 正在优化其云系统的服务器内存容量。系统中有 n 台服务器,其中每台服务器的内存容量用 memory[i] 表示。
系统的服务器数量始终为 偶数,即 2x 台。
其中 x 台为主服务器(primary),另外 x 台为备份服务器(backup)。
每台主服务器 P 都必须配有一台内存容量 ≥ P 的备份服务器 B。
系统的总内存容量为所有主服务器的内存容量之和。
✅ 输入:
一个整数数组 memory,长度为偶数(或可选出偶数数量)。
🎯 目标:
从 n 台服务器中选出 2x 台,使得主服务器和备份服务器满足条件,并使 主服务器的内存总和最大。
🧪 示例:
输入:
memory = [1, 2, 1, 2]
输出: 3
解释:选择 [1,2] 作为主服务器,其它两个为备份,符合条件,总容量为 3。
💡 解题思路(贪心 + 排序):
为了使主服务器的容量总和最大:排序数组 memory。
取前 n // 2 个作为主服务器(小的),后半部分作为备份服务器(大的)。
两者一一配对,必定满足备份服务器容量大于等于主服务器。
主服务器部分即为前半数组的和。
🔹 题目2:调整价格使差值变小
🧩 问题描述:
仓库中有 n 个产品,价格为 prices[i]。现在你需要通过操作,使得最大价格与最小价格的差值 严格小于 d。
你可以进行以下操作任意多次:
选择两个产品 x 和 y,选择整数 p (1 ≤ p ≤ k)。
把产品 x 的价格增加 p
把产品 y 的价格减少 p
✅ 输入:
prices:产品价格数组(1-based 索引)
k:每次操作最多可以增减的幅度
d:目标差值
🎯 目标:
用最少的操作次数使得:
max(prices) - min(prices) < d
🧪 示例:
输入:
prices = [1, 4, 6]
k = 1
d = 2
输出:
2
💡 解题思路(贪心 + 模拟):
不断将最大值减小,最小值增大,让两者逼近直到 max - min < d。
每次可以从最大值减 k,最小值加 k,相当于差值每次最多减少 2k。
因此可以直接模拟或采用堆 + 贪心。
下面是简单贪心模拟方式:
def minOperations(prices, k, d):
from heapq import heappush, heappop, heapify
prices = list(prices)
count = 0
while max(prices) - min(prices) >= d:
max_i = prices.index(max(prices))
min_i = prices.index(min(prices))
delta = min(k, (max(prices) - min(prices)) // 2 or 1)
prices[max_i] -= delta
prices[min_i] += delta
count += 1
return count
✅ 时间复杂度:
题目2数据规模较小(n ≤ 1000),可以接受简单模拟;
如果要更高效,可以使用 max heap 和 min heap 优化找极值操作。