【算法分析】因为不同的小游戏不能准时完成时具有不同的扣款权数,而且是最优解问题,所以本题很容易就想到了贪心法.贪心的主要思想是要让扣款数值大的尽量准时完成.这样我们就先把这些任务按照扣款的数目进行排序,把大的排在前面,先进行放置.假如罚款最多的一个任务的完成期限是k,我们应该把它安排在哪个时段完成呢 应该放在第k个时段,因为放在1～k任意一个位置,效果都是一样的.一旦出现一个不可能在规定时限前完成的任务,则把其扔到最大的一个空时间段,这样必然是最优的,因为不能完成的任务,在任意一个时间段中罚款数目都是一样的本题也可以有另外一种贪心算法,即先把所有的数据按照结束时间的先后排序,然后从前向后扫描. 当扫描到第n个时段,发现里面所分配的任务的结束时间等于n-1,那么就说明在前面这些任务中必须舍弃一个,于是再扫描第1～n这n个时段,挑出一个最小的去掉并累加扣款值,然后再去调整排列顺序,让后面的元素填补前面的空缺,参考资料：http://hi.baidu.com/ya%5Fch%5Fyv/blog/item/cf7f040afce5163db0351d24.html
已赞过已踩过< |
