返回首页 返回题库

饮品调制

C++ 中等 GESP五级真题 #贪心#排序

题目描述

题面描述

你想调制一份甜度恰到好处的饮品给你的朋友们品尝。

有种原料可供用于调制饮品。第种原料存量有升,每升含有克糖分。你可以自由选择原料加入饮品,但每种原料的使用量不得超过其剩余存量。也就是说,假设第种原料选用升,应当有,可以取0到之间的任何数字(包括小数)。

一份甜度恰到好处的饮品需要保证甜度恰好为。最终你调制得到的饮品甜度将为。为了让更多的朋友喝到饮品,请问最多能调制出多少升甜度恰到好处的饮品?如果无法调制出甜度恰到好处的饮品,则认为答案是0。

输入格式

第一行,两个整数,分别表示原料种类数量,恰到好处的甜度。

接下来行,每行两个整数,分别表示第种原料的存量体积、每升含有的糖分质量。

输出格式

一行,一个小数,表示能调制出的甜度恰到好处的饮品最大体积,保留三位小数。

样例1

输入:

4 2
6 1
5 2
8 5
1 0

输出:

14.667

样例2

输入:

2 5
3 4
5 3

输出:

0.000

数据范围

对于40%的测试点,保证。

对于所有测试点,保证,,,。

时间限制

1.0 s

内存限制

512.0 MB

💡 查看提示(先自己想一想再看)
本题考察贪心算法与排序的结合,需要将原料按甜度排序后,分别从低到高和从高到低遍历计算最大可调制体积,注意特殊情况的处理:当所有原料甜度均为t时可以全部使用,当所有原料甜度都高于或低于t时无法调制出符合要求的饮品。
⚙ 开始做这道题 0 人做过 · 0 收藏 · 5 浏览

讨论(0)