贪心算法解决溶液配制问题 - 最优物质含量

贪心算法解决溶液配制问题 - 最优物质含量

题目描述：

实验室需要配制一种溶液。现在，研究员面前有'n'种该物质的溶液，每一种有无限多瓶，第'i'种的溶液体积为'xi'，里面含有'yi'单位的该物质。研究员每次可以选择一瓶溶液，将其倒入另外一瓶（假设瓶子的容量无限)，即可以看作将两个瓶子内的溶液合并。此时合并的溶液体积和物质含量都等于之前两个瓶子内的之和。

特别地，如果瓶子'A'与'B'的溶液体积相同，那么'A'与'B'合并之后该物质的含量会产生化学反应，使得该物质含量增加'X'单位。

研究员的任务是配制溶液体积恰好等于'C'的，且尽量浓的溶液（即物质含量尽量多）。研究员想要知道物质含量最多是多少。

输入描述

第一行三个正整数'n', 'X', 'C'; 第二行'n'个正整数'x1', 'x2', ..., 'Xn'。中间用空格隔开； 第三行'n'个正整数'y1', 'y2', ..., 'yn'，中间用空格隔开。

对于所有数据，1 ≤ 'n', 'X', 'C', 'y¡s' ≤ 1000, 1 ≤ 'xis' ≤ 'C'

数据保证至少存在一种方案能够配制溶液体积恰好等于'C'的溶液。

输出描述

输出一行一个整数，表示答案内容：

思路：

贪心 + 双指针。将每种溶液的体积和物质含量的比值按照从大到小排序，然后从大到小枚举每种溶液，如果加进去溶液体积超过'C'，则尝试减去一些体积较小的溶液，使得总体积等于'C'，同时判断是否有溶液体积等于'C'的情况，若有则特判。在枚举每种溶液时，用双指针维护当前体积最接近'C'的物质含量。