ARC Round#123

已改 ABCD，E 太难写了 /tuu

A

题意：给定 $a, b, c$ 三个数，操作一次可以对一个数 +1，问多少次操作后能变为一个等差数列。

考虑如果 $2 b > a + c$ ，显然只能提升 $c$ 来达成，否则提升 $b$ 是更优秀的选择。处理一下边界即可。

B

题意：给定 $a, b, c$ 三个长度为 $n$ 序列，要求任意序列内重排吗，使得满足 $a_{i} < b_{i} < c_{i}$ 的 $i$ 尽量多。求最大值。 $n \leq 10^{5}$ 。

贪心即可，取最小的 $b_{i} > a_{i}$ ，然后又取最小的 $c_{i} > b_{i}$ ，没有就直接退出。

时间复杂度 $O (n \log n)$ 。

C

题意：给定一个数，他是好的当且仅当十进制下所有数都是 1、2、3 中的一个。给定 $n$ ，问 $n$ 最少可以由多少个好的数加起来构成。 $T (T \leq 1000)$ 组数据， $n \leq 10^{18}$ 。

场上 yy 的，好像和题解做法不太像。

假设我们先不考虑进位问题，那么对于每一位来说，都有一个取数个数的范围，也就是 $[⌈ \frac{x}{3} ⌉, x]$ 。如果这些区间交不为空，那么就取其中的最小值。容易发现不进位合法时一定是最小的情况。

下面考虑一下进位的问题。注意到我们一旦要从上一位偷一个 1 过来，到这里变成了 10，这样的话，这个取数个数的范围至少都是 4 了，这样就可以和前面的有交了。

直接暴力递归计算即可，时间复杂度应该是 $O (\log^{2} n)$ 的，反正很快就是了。

LL solve(LL n)
{
	if (n < 10) return (n + 2) / 3;
	LL pre = solve(n / 10);
	if (pre > n % 10) return std::max(solve(n / 10 - 1), (n % 10 + 12) / 3);
	else return std::max(pre, (n % 10 + 2) / 3);
}

D

题意：将一个序列 $a$ 拆成两个序列 $b, c$ 的和， $b$ 不减， $c$ 不增，问这 $2 n$ 个数绝对值的最小值。 $n \leq 2 \times 10^{5}$ 。

首先我们考虑假设已经知道了 $b_{1}, c_{1}$ ，如何按序构造出后面的项。

如果 $a_{i} \geq a_{i - 1}$ ，则 $c_{i}$ 不变， $b_{i}$ 增加，否则 $b_{i}$ 不变， $c_{i}$ 减少。

容易发现这样构造一定是最优的，因为如果 $a_{i} \geq a_{i - 1}$ ，让 $b_{i}$ 增加， $c_{i}$ 减少，这样肯定不会使绝对值变小，所以不优。

那么我们现在发现 $b_{1}, c_{1}$ 确定的时候我们可以找到一个合法的解。如果我们把 $b_{1}$ 看作变量并把 $b_{1} = 0$ 带入计算得到 $b, c$ ，那么这就是一个 $2 n$ 个绝对值相加的函数，具体的，就是 $\sum_{i = 1}^{n} | x + b_{i} | + | - x + c_{i} |$ 。

赛时 sb 了，我用一个 std::map 维护斜率和截距的实时变化。其实直接找到中位数做一做就好了。这就放一个赛时代码。

using LL = __int128_t;

std::map<LL, LL> kmp, bmp;

int main()
{
	std::cin >> n;
	for (int i = 1; i <= n; ++ i) scanf("%d", a + i);
	c[1] = a[1];
	for (int i = 2; i <= n; ++ i)
		if (a[i] < a[i - 1]) b[i] = b[i - 1], c[i] = a[i] - b[i];
		else c[i] = c[i - 1], b[i] = a[i] - c[i];
	LL del = 1e25;
	for (int i = 1; i <= n; ++ i)
		kmp[-INF] -= 1, kmp[-b[i]] += 2, bmp[-INF] -= b[i], bmp[-b[i]] += 2 * b[i];
	for (int i = 1; i <= n; ++ i)
		kmp[-INF] -= 1, kmp[c[i]] += 2, bmp[-INF] += c[i], bmp[c[i]] -= 2 * c[i];
	for (auto iter = std::next(kmp.begin()); iter != kmp.end(); iter ++) {
		iter->second += std::prev(iter)->second;
	}
	for (auto iter = std::next(bmp.begin()); iter != bmp.end(); iter ++) {
		iter->second += std::prev(iter)->second;
	}
	for (auto [x, k] : kmp) chkmin(del, k * x + bmp[x]);
	std::cout << del << '\n';
	return 0;
}