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 |
这题可以用贪心解决,证明如下:假设牛a、b,距离为a,b,单位时间吃掉的花为da,db。 则先将a运回牛房,a、b共同吃掉的花是ya = a * da + (2 * a + b) * db 先将b运回牛房,a、b共同吃掉的花yb = b * db + (2 * b + a) * da yb - ya = 2 * (b * da - a * db) 当yb > ya, 即(b * da)/(a * db) > 1,即(b/db)>(a/da)时,先先将a运回牛房时间较短。 同理,当yb < ya, 即(b/db)<(a/da)时,现将b运回去时间较短。 当ya == yb时,运哪个都一样。 所以,可以将(x/dx)作为决策变量,这个值较小的先运回去。 Followed by: Post your reply here: |
All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator