本文主要是介绍uva 11729 - Commando War（贪心），希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
题目链接：uva 11729 - Commando War
题目大意：有n个人要去执行任务，第i个人交代任务的时间为Bi，了解完任务之后会不间断的执行Ji分钟，完成所有任务的最短时间。
解题思路：将完成任务需要时间叫长的最先交代，所以只要排序一次然后计算最大时间就可以了。
证明：对于连续的两个人x和y，可以分两种情况：
1.J[x] > B[y] + J[y]时，x先的话，time1 = B[x] + J[x]; 若y先的话，time2 = B[y] + B[x] + J[x]; 很显然time1 < time2.
2.J[x] < B[y] + J[y]时，x先的话，time1 = B[x] + B[y] + J[y]; 若y先的话，time2 = B[y] + B[x] + J[x]; time1 和time2的大小关系主要是看J[x]和J[y].
#include <stdio.h>
#include <string.h>
#include <algorithm>using namespace std;#define max(a,b) (a)>(b)?(a):(b)const int N = 1005;struct job {int b, j;
}s[N];bool cmp(const job& a, const job& b) {return a.j > b.j;
}int n;void input() {for (int i = 0; i < n; i++) scanf("%d%d", &s[i].b, &s[i].j);sort(s, s + n, cmp);
}int solve() {int ans = 0, sum = 0;for (int i = 0; i < n; i++) {ans = max(ans, sum + s[i].b + s[i].j);sum += s[i].b;}return ans;
}int main () {int cas = 1;while (scanf("%d", &n) == 1 && n) {input();printf("Case %d: %d\n", cas++, solve());}return 0;
}
这篇关于uva 11729 - Commando War（贪心）的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
