CF Edu 100D PizzaForces是一道最小花费问题,要求购买若干种不同切片数和价格的披萨,使总切片数不少于n,求最小总花费,解法核心利用披萨切片数均为偶数的特点,先将n向上取整到最近偶数,对较小的n直接枚举所有可能组合;对较大的n,选择性价比(每片价格)更高的披萨批量购买,再微调少量披萨补充不足,这种分情况处理避免暴力枚举低效,以极小复杂度得到更优解,高效解决问题。
背景与大意
Codeforces Educational Round 100的D题《PizzaForces》是一道经典的贪心与枚举结合的问题,考察选手对问题转化和边界优化的能力,题目描述如下:
给定整数n,以及三种披萨的价格:6寸披萨a元、8寸披萨b元、10寸披萨c元,要求购买若干披萨,使得总尺寸≥n,求最小花费(披萨只能整份购买)。
核心思路分析
问题转化
观察到6、8、10均为偶数,若n为奇数,最小满足条件的总尺寸应为n+1(偶数),因此先将n调整为最近的偶数s(s≥n),再将s除以2得到m(即问题转化为:用3、4、5寸的“小披萨”(对应原6、8、10寸)组合,总尺寸≥m,求最小花费)。
枚举与贪心结合
- 小m的处理:当m≤20时,直接枚举所有可能的3、4、5寸披萨数量组合,找到最小花费。
- 大m的处理:当m>20时,更优解必然是选择单位价格更低的披萨(如3寸的单位价格为a/3,4寸为b/4,5寸为c/5),此时只需计算覆盖m所需的该披萨数量(向上取整),即可得到最小花费。
原因:对于大m,单位价格更低的披萨组合能以更低成本覆盖需求,且3、4、5的组合可覆盖所有≥某个阈值的整数,无需额外枚举。
解题步骤
- 调整n为偶数:若n为奇数,n +=1。
- 转化为m:m = n//2。
- 枚举小m:对m≤20,枚举所有可能的3、4、5寸披萨数量,计算最小花费。
- 贪心处理大m:计算三种披萨的单位价格,选择更优的一种,计算覆盖m所需的数量及花费。
- 取最小值:将小m和大m的结果取最小值,即为答案。
代码实现
def minimal_pizza_cost(n, a, b, c):
# Step 1: Adjust n to even if it's odd
if n % 2 != 0:
n += 1
m = n // 2
min_cost = float('inf')
# Step 2: Enumerate all possible combinations for *** all m (<=20)
max_x = m // 3 + 2 # 3-inch pizza count
max_y = m // 4 + 2 # 4-inch pizza count
max_z = m // 5 + 2 # 5-inch pizza count
for x in range(max_x + 1):
for y in range(max_y + 1):
for z in range(max_z + 1):
total_size = 3*x + 4*y + 5*z
if total_size >= m:
current_cost = a*x + b*y + c*z
if current_cost < min_cost:
min_cost = current_cost
# Step 3: Greedy for large m (>20)
if m > 20:
# Calculate unit prices
u1 = a / 3.0
u2 = b / 4.0
u3 = c / 5.0
# Find the best unit price pizza
min_unit = min(u1, u2, u3)
if min_unit == u1:
k, p = 3, a
elif min_unit == u2:
k, p = 4, b
else:
k, p = 5, c
# Number of pizzas needed
t = (m + k - 1) // k # ceil(m/k)
greedy_cost = t * p
min_cost = min(min_cost, greedy_cost)
return min_cost
# Example usage:
# n=10, a=15, b=20, c=25 → expected output 25 (10-inch pizza)
print(minimal_pizza_cost(10,15,20,25))
这道题的关键在于将问题转化为更小的规模(偶数→m),并通过枚举小范围和贪心处理大范围的方式,高效解决了大n的情况,它考察了选手对问题本质的理解和优化能力,是一道值得反复思考的经典题。
通过这道题,我们可以学到:
- 问题转化的重要性(将奇数转化为偶数,简化计算);
- 枚举与贪心的结合(小范围枚举保证正确性,大范围贪心提升效率);
- 单位价格的应用(找到更优性价比的选项)。
希望这篇解析能帮助你理解CF Edu 100D的解题思路,提升编程能力!
