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 |
因为隐藏的题意In Reply To:为什么一定要以1号为起点呢,不能以n为起点 Posted by:lianjianxun at 2010-04-11 15:38:35 flymouse always compared the number of his candies with that of snoopy’s. He wanted to make the difference between the numbers as large as possible while keeping every kid satisfied 因为是班长做主,所以程序必须是从1号为起点,否则如果以n为起点,那就是爱管闲事的那人做主。(具体原因你可想想单源最短路的更新原理) 再举个简单的样例: 2 1 2 5 2 1 6 如果以1为起点得到的答案是5,也就是班长5个糖果,爱管闲事的0个糖果(当然两者可以同时 加上任意的正整数)。如果以2为起点,得到的答案是6,也就是班长得0个,爱管闲事的人得 6个。虽然6比5大,但是根据题意,分配糖果是班长做主,而他是想惩戒爱管闲事者,所以他肯 定会按第一种分配方案分配,所以答案仍旧是5,所以必须以1号为起点。 Followed by: Post your reply here: |
All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator