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

Re:根本不需要你们那些麻烦的证明,看我的证明方法,最简单

Posted by Dr_Ason at 2015-08-06 23:54:51 on Problem 3262
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:
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