Codeforces Round #822 (Div. 2)

A(签到) - Select Three Sticks

题意：

给你一个长度为 n 的正整数序列，你可以操作任意次，每一次操作可以选择任意一个元素，把它 + 1 或者 - 1，问最少多少次操作可以使得序列中存在三个相同的数字以构成一个等边三角形.

思路：

先 sort 一遍，然后取 min 即可. 

参考代码：

void solve() {int n;std::cin >> n;std::vector<int> a(n);for (int i = 0; i < n; i++) {std::cin >> a[i];}std::sort(a.begin(), a.end());int min = (1 << 31) - 1;for (int i = 2; i < n; i++) {min = std::min(min, a[i] - a[i - 2]);}std::cout << min << "\n";
}

B(找规律) - Bright, Nice, Brilliant

题意：

给定一个三角形的金字塔，点亮一部分的砖块，使得每一层的砖块的亮度等于当前层(从高往低)，请构造出一种解使得金字塔满足要求。一个点亮的砖块可以将光传递到下面两个砖块中，一个砖块的亮度为所有能够传递光的砖的数量。

思路：

我们找规律可以发现，只需要让最两侧，也就是金字塔的最外一层点亮，即可让所有砖块的亮度等于当前层数。 

参考代码：

void solve() {int n;std::cin >> n;for (int i = 1; i <= n; i++) {if (i == 1) {std::cout << "1\n";continue;}std::cout << "1 ";for (int j = 1; j <= i - 2; j++) {std::cout << "0\n";}std::cout << "1\n";}
}

C (贪心) - Removing Smallest Multiples

题意：

有集合 S = {1,2,⋯,n}, T，每次操作你可以选择一个 K，然后删除集合中最小且为K的倍数，代价为 K，问最少需要多少代价，能让S变成T。

思路：

贪心。从小枚举每个k，让k尽量取多次，直到遇到一个位置不能删。 

参考代码：

void solve() {int n;std::string t;std::cin >> n >> t;ll ans{};for (int i = 1; i <= n; i++) {for (int j = i; j <= n; j+=i) {if (t[j - 1] == '1') {break;}if (t[j - 1] == '0') {t[j - 1] = '2';ans += i;}}}std::cout << ans << "\n";
}

D(贪心 + 双指针) - Slime Escape

题意：

给定一个数组 a。初始位置为k，血量HP为0。每次可以向右或者向左移动。每到达一个位置，会改变HP增加当前对应位置的值，多次经过一个位置只有第一次会改变HP的值，ai可能是正或者负数，表示HP增加和减少。当HP变成负数时，你就会挂掉。问能否走出两端中的其中一端。 

思路：

贪心+双指针。两种情况是对称的，只需考虑一端出去的情况。不妨设，从右端出去。

每次向右边移动一个位置，就看看左边所有能到达的位置中，能获得的最大血量，则当前能增加的最大血量等于 max(前一个位置能增加的最大血量，当前位置能增加的血量)。

记j为左边能到达的位置，maxval为从k - 1到j中增加的最大血量，left等于a[j]到a[k - 1]的和，i为右边到达的当前位置，right为a[k]到a[i]的和。

maxval即为从k移动到i的过程中，能从左边获取得到的最大的生命值。

• 结论1，如果i - 1能到达maxval所在的位置，则i也能到达该位置 只需在i之前先到达该位置即可。

• 结论2，我们只需关注right非减的位置（最长非减序列），假设这些位置为ps。则maxval只有在属于ps的位置才有可能改变。如果某个位置i不在ps中，则能到达i当且仅当right + maxval >= 0且i - 1可达，我们只需关注x + 1，x+1不属于ps的情况，此时可以从x出发到达maxval所在的位置，而到达x+1时整体血量减少，不可能移动到x能到达的位置的更左端。

• 结论3，y时ps中x的下一个位置，则x能到达的位置，y也能到达。

因此，我们可以双指针进行。i从k开始枚举，对每个i，j依据条件向左移动，同时维护maxval即可。

参考代码：

bool f(std::vector<ll> &a, int k) {ll left = 0, right = 0, maxval = 0;for (int i = k, j = k; i < a.size(); i++) {right += a[i];if (right + maxval < 0) {return false;}while (j - 1 >= 0 && left + a[j - 1] + right >= 0) {left += a[--j];maxval = std::max(maxval, left);}}return true;
}void solve() {int n, k;std::cin >> n >> k;std::vector<ll> a(n);for (int i = 0; i < n; i++) {std::cin >> a[i];}if (k == 1 || k == n || f(a, k - 1)) {std::cout << "Yes\n";return;}std::reverse(a.begin(), a.end());std::cout << (f(a, n - k) ? "Yes" : "No") << "\n";
}