526互联

Educational Codeforces Round 138 (Rated for Div. 2) B. Death's Blessing

发布时间 2023-09-06 14:27:23作者: zsxuan

这是一个电脑游戏，\(n\) 个怪物排成一行，第 \(i\) 个怪物的血量为 \(a_i\) 并且它的亡语强度为 \(b_i\) 。规则是：

  • 玩家每秒可以削减一只怪物的一点血量。
  • 第 \(i\) 只怪物死亡后会释放亡语，它两侧的怪物血量会得到 \(b_i\) 的增幅血量。边界上的怪物只能对它的邻居进行亡语增幅。
  • 一只怪物死亡后，它两侧的怪物变得相邻。

询问最快击杀所有怪物需要多少秒。

观察一：怪物的基础血量不会减少，于是可以直接计算基础血量，再对增幅血量进行讨论。

观察二：最后一只怪物的亡语无效。

观察三：每只怪物迟早要释放亡语，则只让边界上的怪物释放亡语最优。

  • 虽然某一刻存在： \(2 \cdot b_j < b_i\) ，但全局考虑，每个亡语作用一次显然比存在亡语作用两次更优。

于是保证亡语最强的怪物最后死亡，然后从两边随意开始击杀怪物即可。

于是答案为 \(\sum_{i=1}^{n}a_i + \sum_{i=1}^{n}b_i - max_{i=1}^{n}b_i\) 。

这其实是一道：“位置确定情况下，作邻居贡献”的经典题目。

view 
#include <bits/stdc++.h>
void solve() {
	int n; std::cin >> n;
	std::vector<int> a(n), b(n);
	long long sum = 0;
	for (int i = 0; i < n; i++) std::cin >> a[i], sum += a[i];
	for (int i = 0; i < n; i++) std::cin >> b[i], sum += b[i];
	std::cout << sum - *std::max_element(b.begin(), b.end()) << '\n';
}
signed main() {
	int _ = 1; std::cin >> _;
	while (_--) { solve(); }
	return 0;
}