记第 i 种原料的精华份数为 pi,杂质份数为 qi。题目要求在所选原料的精华总份数不低于杂质总份数的前提下,最大化精华总份数。
关键观察:由于 pi+qi=100 且两者均为非负整数,因此 pi 越大,对应的杂质 qi=100−pi 就越小,该原料的“精华‑杂质差值” pi−qi=2pi−100 也越大。显然,我们应该优先选择 pi 较大的原料,因为这样可以在增加精华的同时,尽可能少地增加杂质,更容易满足纯度约束。
基于上述分析,可以采用贪心策略:
一位炼金术士手头有 n 种原料。第 i 种原料由 pi 份精华与 qi 份杂质组成。为了保证炼金产物的纯度,所选原料混合后,精华的总份数不能低于杂质的总份数。术士希望最大化能得到的精华总份数,请你帮他计算这个最大值。
原料的种类数 n 满足 1≤n≤105,对于每种原料,pi 和 qi 均为整数,满足 0≤pi,qi≤100,且总有 pi+qi=100。
第一行包含一个整数 n,表示原料的种类数。 第二行包含 n 个整数 p1,p2,…,pn,依次表示每种原料的精华份数。 第三行包含 n 个整数 q1,q2,…,qn,依次表示每种原料的杂质份数。
By signing up a CodeFun2000 universal account, you can submit code and join discussions in all online judging services provided by us.