自动搬运

查看原文

来自洛谷，原作者为

	pikabi 逝斯以往，斯人不在，留我一人空悲喜

搬运于2025-08-24 22:28:58，当前版本为作者最后更新于2020-12-27 09:47:55，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

---

前言

这题本来 $\color{black}{w}\color{red}{ater\_tomato}$ 写的 std 结果被我爆踩了，所以就有了这篇文章。。

部分分大部分引用其原话，做法也不唯一，想看正解可以直接跳过。

Body

45 pts

Subtask 3

在该范围下，我们所需要求的是在全部高度已知的情况下的答案。我们考虑如何求 $k$ 的最大值和最小值。

首先容易知道，给出的每一个看到的高度其实是这一列的最高的那一格的高度。即若 $a_i=x$，那么该列的 $h_{max}=x$（$h$ 表示高度）。

最大值的情况很好考虑，对于从后往前数第 $i$ 列的从左往右数第 $j$ 个格子 $(i,j)$，只需要取其高度为 $min(b_i,a_j)$ 。容易证明这是可行的方法中 $k$ 最大的。

最小的值的情况略微麻烦一点点。我们考虑，如果存在一个 $b_i=a_j$，我们只需要在格子 $(i,j)$ 放，就可以同时满足这两个值的要求。因此我们考虑先尽可能多的放这样的格子，再把仍然不满足的格子放满即可。显然的，在初步放的过程中，每一个 $b_i$ 或 $a_j$ 都是只能使用一次的，然后无法匹配的再暴力放置。

容易证明，从 $MINN$ 至 $MAXX$ 间的每一个值都是能够取到的。因此答案就是 $MAXX-MINN+1$。

然后我们考虑输出 $0$ 的情况。显然，如果两边的最大值不相等，就是不可行的。

Subtask 2

对于这一种情况，显然 $a_i \le 10$，所以可以暴力枚举每一个 $a_i=-1$ 的值，再乱搞即可。

Subtask 7

我们可以首先考虑输出 $0$ 的情况。显然，如果 $a_{max}>b_{max}$，由于 $b_i\ne-1$ ，所以必然是不可行的。同时，如果其中某一组数据满足 $a_i\ne-1$，就成了 Subtask 3 的情况，此时若 $b_{max}>a_{max}$，也是不可行的。

然后我们考虑如果取 $-1$ 的值。我们可以先将 $b$ 从大到小进行排序，然后对于每一个 $b_i$ 依次进行匹配，如果能够找到相同的，就直接匹配。否则，我们考虑是否需要取一个 $-1$ 将之变为 $b_i$。

首先我们知道，在不考虑匹配的情况下，对于 $a_i=-1$，我们可以取 $a_i=b_{max}$ 使尽可能多的可以该列格子能够放大值。接着我们考虑是否需要使 $a_i=b_i$。我们记贡献 $w$ 为使最大值增加的值减去使最小值增加的值。当 $a_i=b_i$ 时，初值为 $0$。如果取 $a_i=b_{max}$，初值就为 $-b_{max}$。接着我们遍历计算一下贡献，再将之进行比较。

至于为什么每一个 $-1$ 的值一定在 $a_i=b_i$ 和 $a_i=b_{max}$ 中取呢？正确性证明如下:

首先考虑匹配的情况，$a_i=b_i$ 初值一定会为 $0$，我们如果取更小的能够匹配的数，对于其他格子，能够放的高度肯定不会增加只会减少。

对于不匹配的情况，如果取 $a_i=b_{max}-1$，初值也为 $b_{max}-1$，但是我们知道至少存在一个 $b_i=b_{max}$。对于这一格，取 $a_i=b_{max}-1$ 时的贡献为 $b_{max}-1$，而 $a_i=b_{max}$ 的贡献为 $b_{max}$，这样两者就扯平了，而对于其他格子，显然 $a_i$ 取越大，贡献不会减少而有可能增加。

注意，只要找到一次 $a_i=b_{max}$ 的价值大于另一种，容易证明接下来所有的 $a_i=b_i$ 价值也不会高于其，所以直接全部用 $b_{max}$ 覆盖即可。

取完了之后，你需要使用 Subtask 3 中的方法求出最大值与最小值即可。

接着讲一下其他 Subtask：

对于 Subtask 5，你只需要考虑一个 $b_i$ 的情况，帮助你从 $b_i$ 的值上进行考虑，也有一些乱搞算法能过。

100 pts

主视图我们用列，左视图我们用行来表示。

首先我们可以知道，无论是左视图还是主视图，在每个视图中交换第 $i$、$j$ 列 / 行 的高度（同一视图中）对答案是没有影响的，所以我们可以先对于序列 $a$、$b$ 从小到大排个序，以方便我们处理。

因而现在我们有序列 $a$、$b$，$a_1\le a_2\le \ldots \le a_n$ ,$b_1\le b_2 \le \ldots \le b_m$ 。

判断无解的条件很简单，如果左视图最大高度小于主视图最大高度，或者主视图最大高度小于左视图最大高度且没有 $a_i$ 等于 -1 的列，则输出 0。

即

		if(a[n] > b[m]){
			puts("0");
			continue;
		}
		else if(a[1] != -1 && (a[n] < b[m])){
			puts("0");
			continue;
		}

然后我们想，对于主视图和左视图，如果高度都是确定的，那么对于第 $i$ 列第 $j$ 行的交汇处，如果不考虑最高的限制，其可取的范围即为 $0 \sim min(a_i,b_j)$ 。由于行列都有最高限制，我们得在每行每列选择最大值处，固定它的高度，其余所有可活动高度的总和加上 1 就是我们所求的答案。

但是加之以主视图的高度的不确定性，我们不能单纯地枚举其可能性。由于左视图高度都是确定的，我们可以从左视图入手。从大到小枚举每一个高度 $b_j$ 。由于三视图中每行列一定能看到最高高度，故我们钦定左视图第 $j$ 行最高高度出现在主视图第 $i$ 列中，届时就要用到一个匹配的思想。

我们定义

【1】 $i ,j$ 合法 : $b_j \le a_i$ 或 $a_i = -1$ , 即第 $j$ 行最大高度可以出现在第 $i$ 列中。

【2】 $i$ 或 $j$ 已匹配：第 $i$ 列 \ 第 $j$ 行 的最大高度位置已确定。

对于答案贡献我们对每一列一起处理，先预处理出 $b$ 的前缀和 $sum$ 。

显然如果两行的匹配位置同时为第 $i$ 列，且还有第 $k$ 列为匹配且合法，我们可以将其中一行的匹配位置挪到第 $k$ 列中，因为如果 $k$ 列最终闲置未匹配，则不得不自己再钦定最大值，而这样显然不会比挪到第 $k$ 列更优秀。

对于那些 $a_i \ne -1$ 的 $i$ 来说，如果确定了匹配位置 $j$，那么这一列的贡献显然是 $\sum_{b_l \le a_i}{b_l}$ 加上 $\sum_{a_i \le b_l ,j \ne l}{b_j}$ 。

ans += sum[j - 1] + (m - j) * b[j];

如果 $j$ 未匹配，那么只能委屈它放在已匹配的某 $i$ 列中，贡献减少 $b_j$ 。

ans -= b[j];

对于那些 $a_i = -1$ 的 $i$ 来说，如果确定了匹配位置 $j$，它的最高高度也未必是 $b_j$ ，但一定大于等于 $b_j$ 小于等于 $b_m$ ，那么选择 $b_j$ 和选择 $b_{j+1}$ 的贡献差距为 $sum_{j} + (m-j-1)\times b_{j+1} - b_j - sum_{j-1}- (m - j) \times b_j$ （这个时候 $b_{j+1}$ 是确定的所以得减掉），整理一下是 $(m-j-1)\times b_{j+1} - (m-j) \times b_j$ ,这个差的大小我们不清楚；然而对于选择 $b_k$ 和 $b_{k+1}$ （$k > j$）的贡献差为 $b_k + (m-k-1) \times b_{k+1} - (m-k) \times b_k$ ,整理一下为 $(m-k-1)\times (b_{k+1}-b_{k}) \ge 0$ , 由此我们可以知道，如果最高高度不等于匹配位置高度的话，就一定等于 $b_m$，所以答案贡献为：

ans += max(sum[j - 1] + (m - j) * b[j], sum[m - 1] - b[j]);

对于那些未匹配的 $i$ ，直接加上最大贡献就好了。

由于匹配时具有单调性，所以我们在枚举左视图行高时用 $l , r$ 保存当前可匹配的下标范围即可。

最后不要忘了答案加一。

复杂度为 $O(t \times n \times log_n)$ ，瓶颈在sort。

关键代码如下：

int j, l = 1, r = n;
		for(j = m; j >= 1; j--){
			while(l <= r && a[r] > b[j]){
				ans += sum[j] + (m - j - 1) * a[r];
				r--;
			}
			if(l <= r && a[r] == b[j]){
				r--;
				ans += sum[j - 1] + (m - j) * b[j];
			}
			else if(l <= r && a[l] == -1){
				ans += max(sum[j - 1] + (m - j) * b[j], sum[m - 1] - b[j]);
				l++;
			}
			else {
				ans -= b[j];
			}
		}
		while(l <= r){
			if(a[l] == -1){
				ans += sum[m - 1];
			}
			else {
				ans += (m - 1) * a[l];
			}
			l++;
		}
		printf("%lld\n", ans+1);