UVa 11729 - Commando War

题目地址

描述

你有$n$个部下,每个部下需要完成一项任务。第$i$个部下需要你花$B_{i}$分钟交待任务,然后他会立刻独立地、无间断

地执行$J_{i}$分钟任务。你徐亚选择交待任务的顺序,使得所有任务尽早执行完毕(即最后一个执行完的任务应尽早

结束)。注意,不能同时给两个部下交待任务,但是部下可以同时执行他们各自的任务。

每组数据第一行$N(1\leq N\leq 1000)$为部下的人数。以下$N$行每一行有两个正整数$B$和$J$$(1\leq B,J\leq 10000)$,即

交待任务的时间和完成任务的时间。输入结束标志为$N = 0$。

输出完成任务所需的最短的时间。

分析

由题意我们可以很快想到贪心,执行任务所需时间最长的最先交待,那么我们要按照$J$从大到小的顺序依次排序,

然后依次交待。

现在我们用反证法来证明贪心的正确性。

证明

假设我们交换相邻的两个任务$X$和$Y$(交换前$X$在$Y$之前,那么交换后$X$在$Y$之后),我们发现其他任务完成的时

间没有影响,但是对于这两个交换的任务我们有如下两种情况。

情况一,如图一所示。交换前任务$Y$比$X$先结束。交换后$X$结束时间延后,$Y$的结束时间提前了,但是这样交换对

于我们最终的结果非但没有好处反而花费的时间更长了。

情况二,如图二所示。交换前$X$比$Y$先结束,如果交换后情况没有变好,那么一定满足:交换后$X$的结束时间不比

交换前$Y$的结束时间早,也就是说,交换后$Y$的结束时间肯定变早了。所以如图二所示的情况将满足不等式

$B[Y] + B[X] + J[X] \geq B[X] + B[Y] + J[Y]$,化简后得$J[X] \geq J[Y]$,这就是我们贪心的依据。

这里提一下,关于排序的小技巧。(๑•̀ㅂ•́)و✧ 贪心的时候我们经常要用到排序,如果是单个数组排序的话直接$sort$

就可以了。但是如果出现一对数呢?为了避免排序的时候一对数被打散,这时候我们就要用到结构体,因为我们要

对结构体中的元素进行排序,我们把要进行排序的元素在结构体中进行重载,然后把结构体作为$vector$容器中的变

量,然后就可以啦。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
#include <bits/stdc++.h>
using namespace std;

int n;
struct Node{
int b, j;
bool operator < (const Node& rhs) const {
return j > rhs.j;
}
};
vector<Node> vec;

inline int ReadInt(){
int x = 0, f = 1;
char ch = getchar();
while(ch < '0' || ch > '9'){ if(ch == '-') f = -1; ch = getchar();}
while(ch >= '0' && ch <= '9'){ x = x * 10 + ch - '0'; ch = getchar();}
return x * f;
}

int main()
{
int kase = 1;
while(scanf("%d", &n) == 1 && n){
vec.clear();//
int b, j;
for(int i = 0; i < n; i++){
b = ReadInt(); j = ReadInt();
vec.push_back((Node){b, j});
}
sort(vec.begin(), vec.end());
int s = 0, ans = 0;
for(int i = 0; i < n; i++){
s += vec[i].b;
ans = max(ans, s + vec[i].j);
}
printf("Case %d: %d\n", kase++, ans);
}
return 0;
}

开始学习《训练指南》了,加油φ(≧ω≦*)♪

Partager