| ||||||||||
| 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