Codeforces1184B1 the Doctor Meets Vader Easy

原题链接:Codeforces1184B1

题目大意:有许多飞船和星球,飞船有各自攻击值,星球有各自防御值和黄金数,每个飞船可以攻击防御力小于等于自己攻击力的星球并拿到该星球上的黄金,问对于每个飞船最多可以拿多少黄金。

排序

 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
41
42
43
44
45
#include <iostream>
#include <algorithm>

using namespace std;

const int N = 100010;

struct Base {
	int d, g;
	bool operator < (const Base &W) const {
		return d < W.d;
	}
} base[N];

struct Ship {
	int a, pos;
	bool operator < (const Ship &W) const {
		return a < W.a;
	}
} ship[N];

int s, b;
int gold[N];

int main() {
	cin >> s >> b;
	for (int i = 0; i < s; i++) {
		scanf("%d", &ship[i].a);
		ship[i].pos = i;
	}
	for (int i = 0; i < b; i++) scanf("%d%d", &base[i].d, &base[i].g);
   	sort(ship, ship + s);
   	sort(base, base + b);
   	int sum = 0, k = 0; // sum存前缀最大值
   	for (int i = 0; i < s; i++) {
   		gold[ship[i].pos] = sum;
   		while (k < b && base[k].d <= ship[i].a) {	
   			gold[ship[i].pos] += base[k].g;
   			k++;
   		}
   		sum = gold[ship[i].pos];
   	}
   	for (int i = 0; i < s; i++) printf("%d ", gold[i]);
    return 0;
}
updatedupdated2020-05-112020-05-11
加载评论
点击刷新