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:myjfm at 2009-07-24 20:21:17 > 1)将田忌的马按照速度从小到大排序 > 将king的马按照速度从大到小排序 > 2)对田忌的每个马(从小到大扫描),依次和king的每个马(从大到小扫描)比较: > 1:如果能赢,那当然就赢了(因为这是田忌还未参加比赛的最差的马) > 2:如果能平,就尽量平(原因同上) > 3:前两条扫描完后所有的马都赢不了了,只能全输了。 > 这样写,代码也相当简单。这是第一感觉,一次AC,后来又想别贪心方法,都WA,郁闷啊。 我觉得还是有漏洞,就是平局时,为什么能平就尽量平呢?! 就拿楼上的 4 5和6 4举例就可以看出了,如果4平了4,那5就要输给6,结果还要倒贴钱,但是如果5->4,4->6就不用出钱了。这样必然影响后面赢的钱(假如后面还赢钱)。 Followed by: Post your reply here: |
All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator