自动搬运

查看原文

来自洛谷，原作者为

	xuan_never n_n | 3ua

搬运于2025-08-24 21:28:12，当前版本为作者最后更新于2024-05-05 09:49:21，作者可能在搬运后再次修改，您可在原文处查看最新版

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

以下是正文

题目传送门
题意明确，不在此赘述。

思路

我们要根据残留记录，反推出能确定的丢失的记录，求出最多与最少出逃次数。在我们确定了能确定的全部记录后，最少出逃次数即为记录中确定的出逃次数，最多出逃次数则要加上不确定记录的个数。

做法

枚举 $1$ 从 $n$ 至 $1$，对于 $a_{i+1}$ 有记录的，理想 $a_i=a_{i+1}-1$（若 $a_{i+1}$ 记录为 $0$ 也正好使理想 $a_i$ 为 $-1$）。
当 $a_i$ 原本就有记录，但与理想记录不相等时，就出现了记录错误的情况，此时直接输出 -1。

最后记录记录中 $\text{0},\text{-1}$ 的个数即可。

不要忘了记录第一天的出逃哦。

代码

// 码风很丑，勿喷

#include <iostream>
using namespace std;
int n, a[102], ans1, ans2; // ans1记录0，ans2记录-1
int main() {
	cin >> n;
	for (int i = 1; i <= n; ++i)
		cin >> a[i];
	if (~a[1] && a[1]) { // 记录第一天的出逃，也要判断
		cout << -1;
		return 0;
	} a[1] = 0;
	for (int i = n, j; i >= 1; --i) {
		j = (~a[i + 1] ? a[i + 1] - 1 : -1); // 同上，理想ai
		if (~j) {
			if (~a[i] && a[i] != j) {
				cout << -1;
				return 0;
			} a[i] = j;
		} if (!a[i]) ++ans1; // 记录0和-1
		else if (a[i] == -1) ++ans2;
	} cout << ans1 << ' ' << ans1 + ans2;
	return 0;
}

赛前&第一次写题解，RP++。