UVA11729突击战

First blood

UVA11729 Commando War

http://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=456&page=show_problem&problem=2829

题目描述：突击战

你有n个部下，每个部下需要完成一向任务，第i个部下需要花B[i]分钟交代任务，然后他会立即、相互无间断的执行任务J[i]的时间。你需要按照一定顺序交代任务，一边所有任务尽早结束，不能同时给两个部下交代任务，但是他们可以同时做自己的任务。

解题思路：（原先放在博客上的题解太简单了，以至于再看时，都不知道在说什么了）

1、由于一下子难以抽象一个数学模型，我们先举个例子。

B[1] [2] [3] = 1 3 8

J[1] [2] [3] = 4 7 2

假设按照123的顺序布置，动态执行过程是：ans=1+3+11=15

2、按照运筹学分析的三个要素，我们知道：

决策方案：

n个任务，布置顺序不同，带来的效果不同，总统有n！种方案。

限制条件：

任务必需在布置后才能执行，即布置的第i个任务的最早执行事件是 B[1]+B[2],,,,+B[i]，完成时间是B[1]+B[2].....+B[i]+J[i]。注意，这里顺序与输入数据顺序不同。

目标评判标准：

最后一个任务，最后完成时的时间点是最早的。联系上述，即，布置的第i个任务的最早完成时间为B[1]+B[2]....+B[i]+J[i]，所以对于任意决策，我们的我答案是MIN{B[1]+J[1],B[1]+B[2]+...J[2],....,B[1]+B[2]+B[3]....+B[n]+J[n]}。在所有的决策方案中，我们要找到一个使之最小。（联系到决策方案，这个由布置顺序决定）

解决算法：『虽然前面说了很多，但是上面的抽象建模的方法能保证我尽可能一步步找到思路，暂时需要这样做。』

我们最后发现我们发现，关键量是J[n] ，并且最好的情况是第n-1件事在第n件做完前已经完成。所以让前面的任务更早的完成，所以按照J从大到小的顺序排序执行。

PS：在这里的分析还是模糊的，等我学了运筹学再用更科学的方法描述吧.

完整代码：

 1 #include<iostream>
 2 
 3 #include<string.h>
 4 
 5 #include<stdio.h>
 6 
 7 #include<stdlib.h>
 8 
 9 #include<algorithm>
10 
11 #define maxn 1000+10
12 
13 using namespace std;
14 
15 struct point
16 
17 {
18 
19 int b;
20 
21 int j;
22 
23 bool operator< (const point& x) const{
24 
25 return j>x.j;
26 
27 }
28 
29 }a[maxn];
30 
31  
32 
33 int main()
34 
35 {
36 
37 int n;
38 
39 int cas=0;
40 
41 while(~scanf("%d",&n) && n!=0)
42 
43 {
44 
45 cas++;
46 
47 for(int i=0;i<n;i++)
48 
49 {
50 
51 scanf("%d%d",&a[i].b,&a[i].j);
52 
53 }
54 
55 sort(a,a+n);
56 
57 int ans=-1;
58 
59 int add=0;
60 
61 for(int i=0;i<n;i++)
62 
63 {
64 
65 add+=a[i].b;
66 
67 if(add+a[i].j>ans) ans=add+a[i].j;
68 
69 }
70 
71 printf("Case %d: %d
",cas,ans);
72 
73 }
74 
75 return 0;
76 
77 }

关键词：最优决策；贪心

收获：三要素法分析