B3974 [语言月赛 202405] 放行李题解

ShiRoZeTsu · 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';