UVa 11729 Commando War——贪心

UVa 11729 Commando War——贪心

只考虑任务执行时间，则一定要把长的放在前面。

只考虑交代时间，则交代时间不应该有间隙，即交代完一个任务后立刻交代下一个任务，顾交代任务的顺序不影响结果，只有执行任务的时间影响结果，可以贪心

#include #include #include #include using namespace std;const int maxn = 10000 + 10;int n;struct Node { int x, y; bool operator < (const Node &ant) const { return y > ant.y; }}node[maxn];void solve() { int ans = -1; sort(node + 1, node + 1 + n); node[0].x = node[0].y = 0; for (int i = 1; i <= n; i++) { node[i].x += node[i - 1].x; ans = max(ans, node[i].x + node[i].y); } printf("%d\n", ans);}int main(){ int flag = 0; while (scanf("%d", &n) == 1 && n) { for (int i = 1; i <= n; i++) { scanf("%d %d", &node[i].x, &node[i].y); } printf("Case %d: ", ++flag); solve(); } return 0;}

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。