你正在参加一个程序设计竞赛,这次竞赛一共有N道题目,每个题目的难度可以用完成它所需的时间来确定。比赛时每个题目还有一个罚时,等于从比赛开始到你完成此题时所经过的时间,你所有题目的罚时之和叫做总罚时。比赛结束后,所有选手按照总罚时从小到大排名。
这种特殊的比赛规则带来了一个策略问题,就是哪些题应该先做,哪些题应该后做?
比方说,一共有两个题目A、B,难度分别为 30、20 那么,假如你先做A再做B,那么你完成A的时间距比赛开始就是30分钟,于是A的罚时就是30,然后你完成B又用了20分钟,这样完成B时距比赛开始就有30+20=50分钟,于是B的罚时就是50。这样你的总罚时就是30+50=80。
但是假如你先做B再做A呢?不难算出,这样你的总罚时只有70。因此后者是一种更好的比赛策略。
现在,你已经估计出了N道题目大致的难度,请设计一种最好的比赛策略,并计算出该策略下的罚时。