ARC Round#123

已改 ABCD，E 太难写了 /tuu

A

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

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

B

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

贪心即可，取最小的 $b_i>a_i$，然后又取最小的 $c_i>b_i$，没有就直接退出。

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

C

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

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

假设我们先不考虑进位问题，那么对于每一位来说，都有一个取数个数的范围，也就是 $[\lceil {\displaystyle \frac{x}{3}}\rceil ,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$ 不增，问这 $2n$ 个数绝对值的最小值。$n\le 2\times {10}^5$。

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

如果 $a_i\ge a_{i-1}$，则 $c_i$ 不变，$b_i$ 增加，否则 $b_i$ 不变，$c_i$ 减少。

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

那么我们现在发现 $b_1,c_1$ 确定的时候我们可以找到一个合法的解。如果我们把 $b_1$ 看作变量并把 $b_1=0$ 带入计算得到 $b,c$，那么这就是一个 $2n$ 个绝对值相加的函数，具体的，就是 $\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;
}