自动搬运

查看原文

来自洛谷，原作者为

	ShiRoZeTsu AFOed

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

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

以下是正文

Source & Knowledge

2024 年 5 月语言月赛，由洛谷网校入门计划/基础计划提供。

题目大意

给定两个长度为 $n$ 的 $01$ 序列，并给定你两列中其中一个位置，让你找到一个距离最近的位置，并尽可能满足和给定位置在同一列。

题目分析

• 如何求出绝对值

首先，可以写一个函数 int f(int x) 用来求出 $x$ 的绝对值。写法如下：

int f(int x) {
    if(x >= 0) return x;
    return -x;
}

其次，你也可以使用 c++ 自带的绝对值函数，即 abs()，直接就可以求出绝对值了。

• 解决问题

首先，我们可以用二维数组存储这两个 $01$ 序列。这里开一个二维数组 a，用 $a_{0, i}$ 表示左列第 $i$ 个位置，用 $a_{1, i}$ 表示右列第 $i$ 个位置：

int a[2][1000005];

...
  
for(int i = 1; i <= n; i++) cin >> a[0][i];
for(int i = 1; i <= n; i++) cin >> a[1][i];

然后考虑求出答案。我们用 $ans$ 表示最佳位置与 $q$ 的距离，用 $line$ 表示最佳位置所处的列。初始先将 $ans$ 赋值成 $n$，将 $line$ 赋值成 $-1$：

int ans = n, line = -1;

接下来，先循环遍历 $p$ 列（就是给定位置的那一列）上的所有位置。对于任意一个没有行李的位置 $i$，如果 $line = -1$ 或 $ans > |i - q|$，那么可以更新当前的答案，将 $ans$ 赋值为 $|i - q|$，将 $line$ 赋值为 $p$：

for(int i = 1; i <= n; i++) if(a[p][i] == 0)
    if(line == -1 || abs(i-q) < ans) ans = abs(i-q), line = p;

然后循环遍历 $1-p$ 列（就是另外一列）。对于一个没有行李的位置 $i$，如果 $line = -1$ 或 $ans > |i - q|$，那么可以更新当前的答案，将 $ans$ 赋值为 $|i - q|$，将 $line$ 赋值为 $1-p$。

for(int i = 1; i <= n; i++) if(a[1-p][i] == 0)
    if(line == -1 || abs(i-q) < ans) ans = abs(i-q), line = 1-p;

最后，如果 $line$ 的值依旧为 $-1$，那么代表没有可以放行李的位置，直接输出 $-1$；否则，分别输出 $line$ 和 $ans$ 即可：

if(line == -1) cout << -1 << '\n';
else cout << line << ' ' << ans << '\n';

视频讲解