UVA11729突击战（汇报和执行任务）

题意：

你是一个长官，有一些士兵要跟你先汇报任务后在去执行任务，每次只能接受一个人的汇报，但是每一时刻可以有多个士兵在执行任务，问所有任务执行完要的最小时间。

思路：

按执行任务时间从大到小排序来执行就行了，至于为什么贪心的策略是这个我是这么想的，首先任何一个人执行任务的顺序都不会影响他的汇报和干活时间，还有就是

（1）如果两个任务的工作时间相等，汇报时间不同，那么他俩的顺序并不影响最终答案，也就是说汇报时间没什么意义。

（2）如果两个任务的汇报时间相同，工作时间不同，当然是工作时间长的放前面好了<这个可以自己画个图看看>，

（1）+（2）我们可以采取以工作时间长的优先工作的贪心策略。

#include<stdio.h>

#include<algorithm>

#define N 1000 + 5

using namespace std;

typedef struct

{

int a ,b;

}NODE;

NODE node[N];

bool camp(NODE a ,NODE b)

{

return a.b > b.b;

}

int main ()

{

int n ,i ,Ans ,Sum ,cas = 1;

while(~scanf("%d" ,&n) && n)

{

for(i = 1 ;i <= n ;i ++)

scanf("%d %d" ,&node[i].a ,&node[i].b);

sort(node + 1 ,node + n + 1 ,camp);

Ans = Sum = 0;

for(i = 1 ;i <= n ;i ++)

{

Sum += node[i].a;

Ans = Ans < Sum + node[i].b ? Sum + node[i].b : Ans;

}

printf("Case %d: %d\n" ,cas ++ ,Ans);

}

return 0;

}

巴特西

UVA11729突击战（汇报和执行任务）

最新文章

热门文章