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