首页 > 试题广场 >

来硬的

[编程题]来硬的
  • 热度指数：310 时间限制：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 秒，为最优方案。
算法知识视频讲解
添加回答

这道题你会答吗？花几分钟告诉大家答案吧！

提交观点

问题信息

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

热门推荐

相关试题

来硬的

扫一扫，把题目装进口袋

求职之前，先上牛客

扫描二维码，进入QQ群

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