A25229. 计算让 n 组游客（每组 ≤4 人）同时乘坐热气球（每球载客 ≤4 人，同组必须同球）所需的最少热气球数。输入描述：第一行：整数 n（组数，1 ≤ n ≤ 105）第二行：n 个整数（每组人数，1~4），空格分隔。输出描述：输出最少热气球数。样例输入：7 3 2 1 2 1 4 2 样例输出：4
填空题
容易
知识点
题目描述
计算让 n 组游客（每组 ≤4 人）同时乘坐热气球（每球载客 ≤4 人，同组必须同球）所需的最少热气球数。
输入描述：
第一行：整数 n（组数，1 ≤ n ≤ 105）
第二行：n 个整数（每组人数，1~4），空格分隔。
输出描述：
输出最少热气球数。
样例输入：
7
3 2 1 2 1 4 2 样例输出：
4参考答案
n = int(input( ).strip( ))
groups = list(map(int, input( ).split( )))
count1 = groups.count(1) # 1人组
count2 = groups.count(2) # 2人组
count3 = groups.count(3) # 3人组
count4 = groups.count(4) # 4人组
ans = count4 # 4人组必单独一球
ans += count3 # 3人组必一球
count1 -= min(count1, count3) # 用1人组填充3人组球
# 处理2人组：两两配对
ans += count2 // 2
count2 %= 2 # 剩余2人组（0或1）
if count2 == 1: # 剩余1个2人组
if count1 >= 2:
ans += 1
count1 -= 2
elif count1 == 1:
ans += 1
count1 -= 1
else:
ans += 1
# 处理剩余1人组：每4人一球
if count1 > 0:
ans += (count1 + 3) // 4 # 向上取整
print(ans)答案解析
统计各组人数： 分别计数 1、2、3、4 人组。
4 人组： 每组单独一球。
3 人组： 每组一球，并用 1 人组填充（每球最多带 1 个 1 人组）。
2 人组：
优先两两配对（一球载 2 组）。
剩余 1 个 2 人组时：
若有 ≥2 个 1 人组，则组合一球（2+1+1）。
若有 1 个 1 人组，则组合一球（2+1）。
否则，单独一球。
剩余 1 人组： 每 4 人一球（向上取整）。
上一题
下一题