题目大意:有n个士兵,你要给他们没人分配一项任务,对于第i个士兵,你向他描述这个任务需要Bi时间,他完成这个任务需要Ji时间,你描述完了之后他可以独立去完成这个任务,但你一次只能给一个人描述任务,问执行完这n个任务一共需要多少时间。
解题报告:这题利用了贪心的思想,首先我们应该确定应该以什么样的顺序来描述任务,很显然,应该先对完成这个任务时间比较长的士兵描述他的任务,当两个士兵的任务完成需要的时间相同时,描述需要的时间越短就先选择哪个。我们可以定义一个结构体,然后对这个结构体先排一下序,然后就从排序后的第一项开始,定义两个变量,time1,time2,time1表示描述完当前任务的时间,time2表示执行完当前任务之前的所有任务所用的时间,最后time2即为我们要求的值。
1 #include2 #include 3 struct node { 4 int B,J; 5 }sold[1005]; 6 bool cmp(node a,node b) { 7 if(a.J>b.J) 8 return true; 9 if(a.J==b.J)10 return a.B sum)24 sum=time1+sold[i].J;25 }26 printf("Case %d: %d\n",l++,sum);27 }28 return 0;29 }