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 LinJunPing at 2020-07-18 13:57:15 on Problem 3262
   首先假设有a、b两头牛,当先选a时,损失为2*Ta*Db,反之,损失为2*Tb*Da,同时除以Da*Db,可以得到,破坏力衡量指标T/D。
   假设有a1、a2、....、an头牛,且牛的破坏力为a1>a2>a3>....>an,我们假设优先选择破坏力大的牛是一个最优解,当存在一个最优解为ak1,ak2,ak3...akn时,容易知道,当牵走aki和aki+1两头牛时,所花费时间相同,即其他牛所产生的总破坏力相同,如果aki的破坏力<aki+1,我们可以调换两者的顺序,从而得到另一个最优解,接着这个最优解,进一步重复上述过程,从而可以证明优先选择破坏力大的牛是一个最优解

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