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 523064456 at 2015-03-18 19:13:53 on Problem 1700
In Reply To:贪心的正确性,个人理解 Posted by:wukewen at 2014-11-02 17:08:18
> 虽然这个贪心我没想出来。。。
> 
> 考虑当前最慢的人,如果要把它送过去
> 1.可以利用最快的和它一起过去,最快的回来【用别的人显然没有这个优】
> 2.利用船的性质:两个人划船时间取决于最慢的人,那么这个最慢的人过去的时候还可以把次慢的人一起送过去,省的以后再管次慢的人,但这种方案是建立在对岸有个比较快的人能把船划回来的基础上【否则就变成第一种情况了】,我们当然希望划回来的人尽量快,所以应该是最快的在对岸把船划回来,要把最快的人留在对岸就要最快的和次快的一起过去,次快的回来。这样一来,最慢的和次慢的都去了对岸,最快的和次快的又都回到原地,缩小规模,状态不变
> 
> 第二种方案建立在还有大于等于4个人的基础上,最后剩余的特别考虑即可

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