首页 > 试题广场 >

来硬的

[编程题]来硬的
  • 热度指数：632 时间限制：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 单位铁矿石，请计算最少需要多少秒才能全部烧炼完毕。

输入描述:
\hspace{15pt}第一行输入两个整数 n,m\ (1\leqq n\times m\leqq10^6)——煤炭数量与铁矿石总量。接下来 n 行，第 i 行输入两个整数 x_i,y_i：
\hspace{23pt}\bullet\, x_i\ (1\leqq x_i\leqq10^9)——可融化矿石数量；
\hspace{23pt}\bullet\, y_i\ (2\leqq y_i\leqq10^9,\ y_i 为偶数)——燃烧时长。

\hspace{15pt}数据保证 \displaystyle\sum_{i=1}^{n}x_i\geqq m。


输出描述:
\hspace{15pt}输出一个整数，表示烧炼完 m 单位铁矿石所需的最短时间。
示例1

输入

5 28
6 8
5 4
6 10
5 2
6 4

输出

14

说明

\hspace{15pt}选择煤炭 \#1,\#2,\#4,\#5，并对煤炭 \#1 施放魔法：
\hspace{23pt}\bullet\, \#1 升级后燃烧 \tfrac{8}{2}=4 秒，融化 2\times6=12 单位；
\hspace{23pt}\bullet\, \#2 燃烧 4 秒，融化 5 单位；
\hspace{23pt}\bullet\, \#4 燃烧 2 秒，融化 5 单位；
\hspace{23pt}\bullet\, \#5 燃烧 4 秒，融化 6 单位。

\hspace{15pt}总计融化 12+5+5+6=28 单位铁矿石，耗时 4+4+2+4=14 秒，为最优方案。
算法知识视频讲解
开通博客
头像 Coldmou4
发表于 2024-04-28 21:37:11
E 来硬的 dp， 具体请看注释喔 #include <bits/stdc++.h> using LL = long long; using PII = std::pair<LL, LL>; void solve() { LL n, m; std::cin >& 展开全文
去ta的博客 赞 (3) 回复(0) 收起
头像 Silencer76
发表于 2025-08-22 00:47:05
题目链接 来硬的 题目描述 有 枚煤炭和 单位的铁矿石。第 枚煤炭可以融化 单位的铁矿石，燃烧时间为 秒。 你拥有一项魔法，至多可以对一枚煤炭施放，将其升级。若第 枚煤炭被升级，它的融化量变为 ，燃烧时间变为 。 你需要计算出将所有 单位铁矿石烧炼完毕所需的最短时间。 输入: 第一行 展开全文
去ta的博客 赞 (1) 回复(0) 收起
头像 冷艳的西红柿刷牛客
发表于 2025-11-22 11:16:30
#include <iostream> #include <vector> using namespace std; //类似于背包问题，代码逻辑的话和0 - 1背包不同的主要是1.总体积(本题是铁矿石大小)可以超出容量 2.可以选择一个物品升级 //针对超出容量我们只需 展开全文
去ta的博客 赞 (0) 回复(0) 收起
头像 丨阿伟丨
发表于 2025-09-01 13:48:37
HIGH91 来硬的 题目描述 共有 枚煤炭和 单位的铁矿石。第 枚煤炭可以融化 单位的铁矿石，燃烧时间为 秒。 你拥有一项魔法，最多可以对一枚煤炭施放，将其升级。若第 枚煤炭被升级，它将可以融化 单位的矿石，而燃烧时间缩短为 秒。 熔炉同一时刻只能燃烧一枚燃料。请求出将所有 单位 展开全文
去ta的博客 赞 (0) 回复(0) 收起
头像 Infinite_Light
发表于 2025-08-31 14:05:03
题目链接：E-来硬的_牛客小白月赛92 题目分类：常规DP题，是DP各维表示的状态设对，转移方程就可以直接出的那种 思路：看到题目里面有m个煤炭，有n个铁矿，求最小时间 发现没有魔法的时候，就是一个经典的01背包问题 设dp[i][j]=烧了i个煤炭，获得了j个铁矿时所用的最 展开全文
去ta的博客 赞 (0) 回复(0) 收起
头像 练秋湖劣质牛马想当春招糕手
发表于 2025-08-29 11:38:53
对于允许最后一次操作溢出背包，在反向遍历（01背包变种），需要进行max(0, j-weight)限制对于有额外操作的情况，最后不要降维，可能会因为重复访问引起错误，直接二维解决即可。 #include <algorithm> #include <climits> #incl 展开全文
去ta的博客 赞 (0) 回复(0) 收起

问题信息

来自：华为机试编程模拟题10
难度：
0条回答 402浏览

热门推荐

相关试题

来硬的

扫一扫，把题目装进口袋

求职之前，先上牛客

扫描二维码，进入QQ群

扫描二维码，关注牛客公众号