2020.07.27 2020牛客暑期多校训练营（第六场）

无

无

Fraction Construction Problem

https://ac.nowcoder.com/acm/contest/5668/F

分类：数学

这题考察的数学知识很棒，证明也很精彩，所以作为推荐题目。

题目大意：给定两个整数$a,b$，找出四个整数$c,d,e,f$满足：

（1）$\frac{c}{d}-\frac{e}{f}=\frac{a}{b}$

（2）$d<b$且$f<b$

（3）$1\le c,e \le 4 \times 10^{12}$

思路：题目可能比较长，但其实矛盾点就是在蛤蜊*1的笼子应该是拿去作饲料还是拿去捕捉鱼。这里有两种解法。

比赛的时候我使用倒序读取，need记录目前所需的饲料。碰到空笼子则need++，碰到有蛤蜊的笼子分两种情况（1）need==0时用于捕捉鱼（2）need!=0时用于做饲料。有鱼的笼子全部捉鱼即可。

第二种是顺序读取，贪心把所有的蛤蜊做成饲料，最后把剩下的饲料/2，一半用于做饲料，一半用于捉鱼。

无

无

无