我要招人

去企业版

首页 > 试题广场 >

来硬的

[编程题]来硬的

热度指数：1129 时间限制：C/C++ 1秒，其他语言2秒空间限制：C/C++ 256M，其他语言512M
算法知识视频讲解

$\hspace{15pt}$ $\hspace{15pt}$ $\hspace{15pt}$ $\hspace{15pt}$

$\hspace{15pt}$ 你厌倦了探索的日子，背包中堆满了铁矿石，准备放进熔炉烧炼。共有 $n$ 枚煤炭可供使用，第 $i$ 枚煤炭具有：
$\hspace{23pt}\bullet\,$ 可在熔炉中燃烧 $y_i$ 秒；
$\hspace{23pt}\bullet\,$ 最多融化 $x_i$ 单位铁矿石。

$\hspace{15pt}$ 你掌握一项魔法，至多对一枚煤炭施放，将其升级为暗物质燃料。若第 $i$ 枚煤炭被升级，则：
$\hspace{23pt}\bullet\,$ 燃烧时间变为 $\tfrac{y_i}{2}$ 秒；
$\hspace{23pt}\bullet\,$ 可融化的矿石数量变为 $2x_i$ 单位。

$\hspace{15pt}$ 熔炉同一时刻只允许燃烧一枚燃料；燃料耗尽之前，无法取出已融化的矿石。每枚燃料仅能使用一次。

$\hspace{15pt}$ 现在你拥有 $m$ 单位铁矿石，请计算最少需要多少秒才能全部烧炼完毕。

输入描述:

第一行输入两个整数 ——煤炭数量与铁矿石总量。接下来  行，第  行输入两个整数 ：
 ——可融化矿石数量；
  为偶数——燃烧时长。

数据保证 。

输出描述:

输出一个整数，表示烧炼完  单位铁矿石所需的最短时间。

示例1

输入

输出

说明

选择煤炭 ，并对煤炭  施放魔法：
  升级后燃烧  秒，融化  单位；
  燃烧  秒，融化  单位；
  燃烧  秒，融化  单位；
  燃烧  秒，融化  单位。

总计融化  单位铁矿石，耗时  秒，为最优方案。

算法知识视频讲解

Python

面试中的废话选手

n, m = list(map(int, input().split())) 
original_m = m 
lis = []
for _ in range(n):
    cur = list(map(int, input().split()))
    lis.append(cur)
#先选效率最高的煤
lis.sort(key = lambda x:(x[0]/x[1]))
t = 0 
li = []
res = float("inf")
while m > 0:
    cur = lis.pop()
    li.append(cur)
    m -= cur[0]
    t += cur[1]
    # 每取一块煤就尝试升级所有已选煤 
    for k in range(len(li)):
        i = li[k]
        # 升级后总融化量足够的判断 
        if (original_m - m) + i[0] >= original_m:
            new_sum_x = (original_m - m) + i[0]
            new_t = t - i[1] // 2 
            # 从最后一块（效率最低）开始去掉多余的煤 
            j = len(li) - 1 
            while j >= 0:
                if j == k:  # 不能去掉正在升级的煤 
                    j -= 1 
                    continue 
                if new_sum_x - li[j][0] >= original_m:
                    new_sum_x -= li[j][0]
                    new_t -= li[j][1]
                j -= 1 
           
            res = min(res, new_t)
print(res)


10/11 组用例通过

编辑于 2026-05-24 22:30:48 回复(0)