Online JudgeProblem SetAuthorsOnline ContestsUser
Web Board
Home Page
F.A.Qs
Statistical Charts
Problems
Submit Problem
Online Status
Prob.ID:
Register
Update your info
Authors ranklist
Current Contest
Past Contests
Scheduled Contests
Award Contest
User ID:
Password:
  Register

这题可以用贪心解决,证明如下:

Posted by lunning at 2015-07-18 23:00:33 on Problem 3262
假设牛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:
User ID:
Password:
Title:

Content:

Home Page   Go Back  To top


All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator