| 题目名称 | 1446. [UVa 11729] 突击战 |
|---|---|
| 输入输出 | commando.in/out |
| 难度等级 | ★ |
| 时间限制 | 1000 ms (1 s) |
| 内存限制 | 64 MiB |
| 测试数据 | 5 |
| 题目来源 |
 超级傲娇的AC酱
于2013-11-23加入 |
| 开放分组 | 全部用户 |
| 提交状态 | |
| 分类标签 | |
| 分享题解 |
| 通过：101， 提交：178， 通过率：56.74% | ||||
 new ioer |
100 | 0.052 s | 4.05 MiB | C++ |
 kZime |
100 | 0.057 s | 0.56 MiB | C++ |
 LGLJ |
100 | 0.058 s | 0.63 MiB | C++ |
 Janis |
100 | 0.071 s | 0.26 MiB | C++ |
 test |
100 | 0.087 s | 0.32 MiB | C++ |
 king'back |
100 | 0.090 s | 0.31 MiB | C++ |
|
king'back |
100 | 0.090 s | 0.31 MiB | C++ |
 雾茗 |
100 | 0.094 s | 0.32 MiB | C++ |
 rpCardinal |
100 | 0.101 s | 0.30 MiB | C++ |
|
rpCardinal |
100 | 0.101 s | 0.30 MiB | C++ |
| 关于 突击战 的近10条评论(全部评论) | ||||
|---|---|---|---|---|
|
贪心，n个士兵，n个任务。。。。
数据过水。。。。 | ||||
|
这题需要证一个贪心性质：总是优先布置执行时间长的任务可以得到最优解。
首先考虑最后一个任务。因为所有任务是连续交待的，所以 最后一个任务完成的时间=所有任务的布置时间之和+最后一个任务的布置时间。 很显然，若最后一个任务执行的时间不是最短的，则把执行时间最短的任务和最后一个任务交换，所得的方案至少不会更差。 所以执行用时最短的任务要放在最后交待。 前面的(n-1)个任务也满足这个性质，证毕。（毫不严谨。。。） | ||||
|
| ||||
|
| ||||
|
VIP 好屌
| ||||
|
这题都不用重载运算符
| ||||
|
回复 @Mike's learning :
请看标题下的文件名：commando.in/out。由于题库中题目文件名不能重复因此可能与原题有别  cstdio
2013-11-24 22:36
2楼
| ||||
|
输入输出文件到底该叫啥名字啊！
 FoolMike
2013-11-24 16:05
1楼
| ||||
liu_runda
筽邝
digital-T
OI永别
752199526【题目描述】
你有$n$个部下，每个部下需要完成一项任务。第$i$个部下需要你花$B_i$分钟交代任务，然后他会立刻独立地，无间断的执行$J_i$分钟后完成任务。你需要交代任务的顺序，使得所有的任务尽早执行完毕。注意，不能同时给2个部下交代任务，但是部下可以同时执行各自的任务。
【输入格式】
输入数据包括多组数据，每组数据的第一行为部下的个数N(1≤N≤1000)；以下N行有2个正整数B和J(1≤B≤1000,1≤J≤1000),即交代任务的时间和执行任务的时间。输入结束标志符为N=0。
【输出格式】commando.in
对于每组数据，输出(以第i组数据为例)：
Case i: Time
【样例输入】commando.out
3 2 5 3 2 2 1 3 3 3 4 4 5 5 0
【样例输出】
Case 1: 8 Case 2: 15
【来源】
From UVa 11729 Commando War