Gravatar
king'back
积分:528
提交:600 / 1219
贪心,n个士兵,n个任务。。。。
数据过水。。。。

Gravatar
liu_runda
积分:2890
提交:1014 / 2190
这题需要证一个贪心性质:总是优先布置执行时间长的任务可以得到最优解。
首先考虑最后一个任务。因为所有任务是连续交待的,所以 最后一个任务完成的时间=所有任务的布置时间之和+最后一个任务的布置时间。
很显然,若最后一个任务执行的时间不是最短的,则把执行时间最短的任务和最后一个任务交换,所得的方案至少不会更差。
所以执行用时最短的任务要放在最后交待。
前面的(n-1)个任务也满足这个性质,证毕。(毫不严谨。。。)

Gravatar
筽邝
积分:1128
提交:558 / 983

Gravatar
digital-T
积分:2215
提交:586 / 1311

Gravatar
OI永别
积分:566
提交:240 / 406
VIP 好屌

Gravatar
752199526
积分:275
提交:118 / 282
这题都不用重载运算符

Gravatar
cstdio
积分:4755
提交:1198 / 2108
回复 @Mike's learning :
请看标题下的文件名:commando.in/out。由于题库中题目文件名不能重复因此可能与原题有别

题目 1446 [UVa 11729] 突击战
2013-11-24 22:36:45
Gravatar
FoolMike
积分:5200
提交:1165 / 2240
输入输出文件到底该叫啥名字啊!

题目 1446 [UVa 11729] 突击战
2013-11-24 16:05:03