P14269 兄妹

· · 算法·理论

题解：P14259 兄妹（siblings）

题目大意

书店有若干排书架，第 r 排书架包含坐标 (r, c)（c \ge 0），出入口在 (r, 0)。有 n 本书需要放到指定位置 (r_i, c_i)。两个人从 (0,0) 出发，各自负责一部分书，放书后返回 (0,0)。移动规则：

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

解题思路

关键观察

  1. 每排的最远距离：对于同一排 r，如果有多本书，只需要考虑最远的那本，因为在同一排内移动可以顺便放其他书。设 x_r = \max\{c_i \mid r_i = r\}，如果该排没有书，则 x_r = 0。

  2. 总用时计算：如果一个人负责的集合 A 包含排号 r_1, r_2, \dots, r_k，那么他的用时为：

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

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

  1. 问题转化：设最大排号为 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。

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

设 f[j] 表示前 i 排中能否选出一个子集，使得其 x_i 之和为 j。我们遍历排号 i 从 1 到 m，更新背包。对于每个 i，我们考虑前 i 排的子集和 j，那么此时：

则用时为 \max(i + j, m + c - j)。我们取所有可能中的最小值。

算法步骤

  1. 预处理每排的 x_r。
  2. 找到最大排号 m。
  3. 计算总距离和 c = \sum_{r=1}^m x_r。
  4. 初始化背包数组 f，大小为 c+1，f[0] = 1。
  5. 初始化答案 ans 为一个较大值。
  6. 对于 i 从 1 到 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)。
  7. 输出 2 \times ans。

复杂度分析

代码实现


#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;
}