题解：P14259 兄妹（siblings）

题目大意

书店有若干排书架，第

r

排书架包含坐标

(r, c)

（

c \ge 0

），出入口在

(r, 0)

。有

n

本书需要放到指定位置

(r_i, c_i)

。两个人从

(0,0)

出发，各自负责一部分书，放书后返回

(0,0)

。移动规则：

在同一排内，可以上下移动。
在不同排之间，只能通过出入口移动。

求两人中用时较长者的最短用时。

解题思路

关键观察

每排的最远距离：对于同一排 $r$ ，如果有多本书，只需要考虑最远的那本，因为在同一排内移动可以顺便放其他书。设 $x_r = \max\{c_i \mid r_i = r\}$ ，如果该排没有书，则 $x_r = 0$ 。
总用时计算：如果一个人负责的集合 $A$ 包含排号 $r_1, r_2, \dots, r_k$ ，那么他的用时为：

2 \times \left( \max_{i \in A} r_i + \sum_{i \in A} x_i \right)

因为需要走到最远的排，并且每排都需要来回。

问题转化：设最大排号为 $m$ 。我们需要将排 $1, 2, \dots, m$ 分成两个集合 $Y$ 和 $S$ ，使得：

\max \left( \max(Y) + \sum_{i \in Y} x_i, \max(S) + \sum_{i \in S} x_i \right)

最小。由于

m

是最大排号，必然有一个集合包含

m

，不妨设

Y

包含

m

，则

\max(Y) = m

。另一个集合

S

的排号均不超过

m-1

，设

s = \max(S)

。

那么问题转化为：求

\min \max \left( m + \sum_{i \in Y} x_i, s + \sum_{i \in S} x_i \right)

其中

Y \cup S = \{1, 2, \dots, m\}

，

Y \cap S = \emptyset

，且

m \in Y

。

动态规划：设总距离和 $c = \sum_{i=1}^m x_i$ 。我们枚举 $s$ （即 $S$ 的最大排号），但更高效的方法是使用背包 DP 计算所有可能的子集和。

设

f[j]

表示前

i

排中能否选出一个子集，使得其

x_i

之和为

j

。我们遍历排号

i

从

1

到

m

，更新背包。对于每个

i

，我们考虑前

i

排的子集和

j

，那么此时：

$S$ 由前 $i$ 排中的若干排组成，最大排号为 $i$ ，距离和为 $j$ 。
$Y$ 包含后 $m-i$ 排以及前 $i$ 排中未选中的排，距离和为 $c - j$ ，最大排号为 $m$ 。

则用时为

\max(i + j, m + c - j)

。我们取所有可能中的最小值。

算法步骤

预处理每排的 $x_r$ 。
找到最大排号 $m$ 。
计算总距离和 $c = \sum_{r=1}^m x_r$ 。
初始化背包数组 $f$ ，大小为 $c+1$ ， $f[0] = 1$ 。
初始化答案 $ans$ 为一个较大值。
对于 $i$ $i$ 从 $1$ $1$ 到 $m$ $m$ ：
- 如果 $x_i > 0$ ，则从后往前更新背包：对于 $j$ 从 $c$ 到 $0$ ，如果 $f[j]$ 为真，则设置 $f[j + x_i]$ 为真。
- 然后遍历所有 $j$ 从 $0$ 到 $c$ ，如果 $f[j]$ 为真，则计算 $t = \max(i + j, m + c - j)$ ，并更新 $ans = \min(ans, t)$ 。
输出 $2 \times ans$ 。

复杂度分析

时间复杂度： $O(m \cdot c)$ ，其中 $m$ 是最大排号， $c$ 是总距离和。由于 $m \le 500$ ， $c \le 500 \times 500 = 250000$ ，但实际中 $c$ 可能较小，因为每排的 $x_r$ 不会都很大。
空间复杂度： $O(c)$ ，使用一维背包数组。

代码实现

CPP

#include <iostream>
#include <algorithm>
#include <cstring>
using namespace std;

const int MAX_R = 500;
const int MAX_SUM = 250000;

int x[MAX_R + 1];
bool f[MAX_SUM + 1];

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    
    int T;
    cin >> T;
    while (T --) {
        memset(x, 0, sizeof(x));
        memset(f, 0, sizeof(f));
        int n;
        cin >> n;
        int max_r = 0;
        for (int i = 0; i < n; i ++) {
            int r, c;
            cin >> r >> c;
            x[r] = max(x[r], c);
            max_r = max(max_r, r);
        }
        
        int r = max_r;
        while (r > 0 && x[r] == 0) r --;
        int total_c = 0;
        for (int i = 1; i <= r; i++) {
            total_c += x[i];
        }
        
        f[0] = true;
        int ans = 300000;
        int s = 0;
        for (int i = 1; i <= r; i ++) {
            if (x[i] == 0) continue;
            for (int j = s; j >= 0; j --) {
                if (f[j]) {
                    f[j + x[i]] = true;
                }
            }
            s += x[i];
            for (int j = 0; j <= s; j ++) {
                if (f[j]) {
                    ans = min(ans, max(i + j, r + total_c - j));
                }
            }
        }
        cout << ans * 2 << '\n';
    }
    
    return 0;
}

P14269 兄妹

文章操作