AtCoder Beginner Contest 127 题解

AC Codes

A – Ferris Wheel

B – Algae

C – Prison

D – Integer Cards

有 $N$ 张卡片，每张卡片上有一个数字 $A_i$ ，现在你有 $M$ 次操作，每次操作你都可以选择不超过 $B_j$ 张卡片，将这些卡片上的数字改写为 $C_j$ 。请问最终所有卡片上数字之和的最大值？

$N,M\leq 10^5$ 。

很显然只需要用一个堆维护前 $N$ 大的值。

E – Cell Distance

在一个 $N\times M$ 的棋盘上放 $K$ 枚棋子。计算对于所有不同的棋子摆放方案：
$$
\sum_{i=1}^{K-1}\sum_{j=i+1}^K(|x_i-x_j|+|y_i-y_j|)
$$
的和（第 $i$ 枚棋子的坐标为 $(x_i,y_i)$）。

$2\leq K\leq N\times M\leq 2\times 10^5$ 。

由于是曼哈顿距离之和，因此 $x$ 坐标和 $y$ 坐标可以看作两个独立的子问题，可以分开来处理。

我们只考虑纵坐标的情况（横坐标同理），然后从局部入手，我们固定两个棋子，那么剩下的 $K-2$ 个棋子一共有 $\binom{NM-2}{K-2}$ 种摆法，不妨枚举这两个棋子之间距离为 $d$ ，那么这两个棋子的摆法就是 $(N-d)M^2$ 。因此，本题的结论为：
$$
\binom{NM-2}{K-2}(\sum_{d=1}^{N-1}(N-d)M^2+\sum_{d=1}^{M-1}(M-d)N^2)
$$

F – Absolute Minima

函数 $f(x)$ 初始为 $0$ ，进行 $Q$ 次操作，操作一共有两种：

1. 给定 $a,b$ ，然后给 $f(x)$ 加上 $|x-a|+b$ 。
2. 询问当前 $f(x)$ 的最小值和最小值所处的横坐标的最小值。

$Q\leq 2\times 10^5,10^{-9}\leq a,b\leq 10^9$ 。

首先很容易发现加上的 $b$ 一定会让最小值增大 $b$ ，因此我们很容易处理，本题实际上就是在询问 $\sum |x-a_i|$ 的最小值。

这是一个经典问题，答案是：如果函数 $f(x)=\sum_{i=1}^n|x-a_i|$ 取到最小值，那么 $x_{\min}$ 一定是数列 ${a_1,a_2,\ldots,a_n}$ 的中位数。因此我们要做的就是动态维护中位数，这也是一个经典问题，可以用两个堆维护。

假设中位数是 $x$ ，那么我们一共有这样两个堆：一个小根堆，堆中的元素 $\ge x$ （不包括中位数 $x$ 本身）；一个大根堆，堆中的元素 $\le x$ （不包括中位数 $x$ 本身）。然后我们只需要始终保证小根堆的大小等于大根堆的大小或者小根堆的大小等于大根堆的大小+1。