2021-02-19--突击战（Commando War, UVa 11729）
最近也是又看起了算法入门，算是锻炼一下许久没有好好思考的脑子吧！
突击战（Commando War, UVa 11729）
你有n个部下，每个部下需要完成一项任务。第i个部下需要你花Bi分钟交待任务，然后他会立刻独立地、无间断地执行Ji分钟后完成任务。你需要选择交待任务的顺序，使得所有任务尽早执行完毕（即最后一个执行完的任务应尽早结束）。注意，不能同时给两个部下交待任务，但部下们可以同时执行他们各自的任务。
【输入格式】
输入包含多组数据，每组数据的第一行为部下的个数N（1≤N≤1 000）；以下N行每行两个正整数B和J（1≤B≤10 000，1≤J≤10 000），即交待任务的时间和执行任务的时间。输入结束标志为N=0。
【输出格式】
对于每组数据，输出所有任务完成的最短时间。
【样例输入】
3
2 5
3 2
2 1
3
3 3
4 4
5 5
0
【样例输出】
Case 1: 8
Case 2: 15
那个书上的代码是：（不过我没有运行成功）
#include<cstdio>
#include<vector>
#include<algorithm>
using namespace std;
struct Job {
int j, b;
bool operator < (const Job& x) const { //运算符重载。不要忘记const修饰符
return j > x.j;
}
};
int main() {
int n, b, j, kase = 1;
while(scanf("%d", &n) == 1 && n) {
vector<Job> v;
for(int i = 0; i < n; i++) {
scanf("%d%d", &b, &j); v.push_back((Job){j,b});
}
sort(v.begin(), v.end()); //使用Job类自己的 < 运算符排序
int s = 0;
int ans = 0;
for(int i = 0; i < n; i++) {
s += v[i].b; //当前任务的开始执行时间
ans = max(ans, s+v[i].j); //更新任务执行完毕时的最晚时间
}
printf("Case %d: %d\n", kase++, ans);
}
return 0;
}
并且上面还给了一句充满玄学的话语：直觉告诉我们，执行时间较长的任务应该先交待。这话说出来真的是，无语了！
后面也是找了好多篇文章，后来明白了一件事情，不管你是怎么样安排的，你都要明白一个东西，就是你交待事情的时间是不变的，部下们完成这些事情的时间也是固定的，并且它们什么时候完成事件还与你的交待事件密切相关，这个时候我们要尽最大努力保证你从最开始就在交待事情，并且用最快的速度交待完毕是比较好的，那么怎么样安排交待事情的长度呢？如果你交待一件事情它所需要的执行事件比较长，在这段时间你可以去交待很多的事情比较好，还是你每次都交代一个所需执行时间比较短的事情，在你还没有交待完成下一个事情的时候它就完成了好呢？我想答案是显而易见的，就是把它们用执行事件的长短排序，然后去交待执行。
所以我们明白了一件事情就是先要按照执行时间排序，然后按照这个顺序，一个一个交待。
下面是一个比较好理解的代码：
#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;
struct Job //定义一个结构体
{
int b; //交代任务的时间
int j; //执行任务的时间
};
bool cmp(Job a, Job b)//定义一个比较方法
{
return a.j>b.j;
}
int main()
{
int n, j, b, Case = 1;//n表示多少个部员
while (cin >> n&&n != 0)
{
vector<Job> v;
for (int i = 0; i<n; i++)
{
cin >> b >> j;
v.push_back(Job{ b, j });
}
sort(v.begin(), v.end(), cmp); //按照J从大到小排序 参数表在下面
int s = 0;
int ans = 0;
for (int i = 0; i<n; i++)
{
s += v[i].b; //当前任务的开始执行时间（即直到交代完这个任务所花的的时间）
ans = max(ans, s + v[i].j); //更新任务执行完毕所花的时间
}
cout << "Case " << Case++ << ": " << ans << endl;
}
return 0;
}
sort( I first, S last, Comp comp = Comp{}, Proj proj = Proj{} );
sort参数
first, last - 要排序的元素范围
rng - 要排序的元素范围
comp - 要使用的比较器
proj - 要应用到范围中元素的投影
for (int i = 0; i<n; i++)
{
s += v[i].b;
ans = max(ans, s + v[i].j);
}
这段代码其实很好理解的，就是我们来想象一下，最终的结果只有两种可能性，就是要么就是你最后交待的一件事情已经完成了但是原来交待过的事情还没有完成这个时候你就需要等全部完成然后确定这个时间；另外一种可能性就是最后完成的事情是你最后交待的事情所以这个就是保证所有事情的完成的最后时间。
还是慢慢学吧！学会怎么样分析，分解、解析事件是比较重要的事情。