Online Judge | Problem Set | Authors | Online Contests | User | ||||||
---|---|---|---|---|---|---|---|---|---|---|
Web Board Home Page F.A.Qs Statistical Charts | Current Contest Past Contests Scheduled Contests Award Contest |
Re:根本不需要你们那些麻烦的证明,看我的证明方法,最简单In Reply To:根本不需要你们那些麻烦的证明,看我的证明方法,最简单 Posted by:caoyuan0816 at 2014-02-10 01:24:02 > 任意一头牛,例如: > 2 7 > 可以看成两头 1 3.5的牛 > 也就是说任意一头牛都可以拆成T头 > 1 D/T > 的牛 > 所以说,所有的牛就都变成了 > 1 X > 那是否应该就X从大到小排序,用优先队列搞定呢? > :)还需要哪些复杂的证明吗? 我觉得有更简单的方法,一个sort就行。 证法如下: 取最前面的两头牛a、b,设其耗时量和食草量分别为Ta、Tb、Da、Db,剩下的牛总食草量为D,a在前的总消耗为 S1,b在前的总消耗为 S2,则: S1 = 2 * ( D * ( Ta + Tb ) + Db * Ta ), S2 = 2 * ( D * ( Ta + Tb ) + Da * Tb ). 故sort的比较函数为 bool cmp( cow a, cow b){ return Ta * Db < Da * Tb; } Followed by: Post your reply here: |
All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator