题目链接:http://202.197.224.59/OnlineJudge2/index.php/Contest/read_problem/cid/43/pid/1268
题意
定义一个函数:f(t)=min(i,j∈ℤ)|i/n−j/m+t|,给出n和m,求使得f(t)最大的t的取值。(式子可以查看原网页中的式子)
题解
因为i,j都是可以取任意整数的,所以进行式子中的前两个部分进行通分以后就是(im-jn)/mn。
观察我们可以得到要得到最大值t的值就是上述式子的最小精度的一半,求最小精度就是要求分子(im-jn)能表示的数的间隔
这个间隔我用一个比较巧妙的方法求得,用一个优先队列来存放这两个数,不断从优先队列中取出两个最小的数做差,然后再放入优先队列中,直到取出的这两个最小的数是相同的。
最后对得到的分数进行化简就是最后的答案了
代码
1 |
|
小结
做出这道题的时候还是有些激动的,因为在现场赛上两题如果罚时不多的话就是铜牌。哈哈,如果我去打这场比赛就能够拿一个铜牌。
好好努力,提升实力,以后在区域赛上拿牌就美滋滋了。