首页 > 代码库 > UVa11729 - Commando War
UVa11729 - Commando War
题意
有n个士兵，每个士兵需要花b秒交代任务，j秒完成任务，现需选择交代任务的顺序，使整个任务花费时间最短。不能同时交代任务，但士兵可同时执行各自的任务。
思路
先排序，从执行时间最长的开始交代任务，然后贪心？仍旧不懂什么是贪心，书上写这是贪心，那就是贪心吧=。=
s+v[i].j是到第i个士兵的b的总和加上第i个士兵的j，再与之前的ans比较，取较大的赋值给ans
总结
C++还没系统的学习，对operator不是很了解，先搞明白大概的格式是什么样的就好啦，做题的时候就是卡在了怎么排序上，看了下训练指南上的代码，以后就会排结构体的大小顺序啦。
构造函数也不是很懂，一和vector在一起就不知道怎么传参了，先记住记住记住。
1 #include <iostream> 2 #include <cstdio> 3 #include <vector> 4 #include <algorithm> 5 using namespace std; 6 struct job 7 { 8 int b,j; 9 job(int m,int n):b(m),j(n){}10 bool operator < (const job &x) const {11 return j < x.j;12 }13 };14 int main()15 {16 int n,Case = 0;17 while(scanf("%d",&n)== 1 && n) {18 vector<job>v;19 int b,j;20 for(int i = 0; i < n; i++) {21 cin >> b >> j;22 v.push_back((job){b,j});23 }24 sort(v.begin(),v.end());25 reverse(v.begin(),v.end());26 int ans = 0,s = 0;27 for(int i = 0; i < n; i++) {28 s += v[i].b;29 ans = max(ans, s+v[i].j);30 }31 printf("Case %d: %d\n",++Case,ans);32 }33 return 0;34 }
1 /*蓝书上是这么写的*/ 2 for(int i = 0; i < n; i++) { 3 cin >> b >> j; 4 v.push_back((job){b,j}); //这样写就不用写结构体中的构造函数了 5 } 6 7 8 //直接把 < 重载成 > ，这样sort时就直接是j从大到小的排列，不需要reverse函数了 9 bool operator < (const job &x) const { 10 return j > x.j;11 }
UVa11729 - Commando War
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。