跷跷板问题题解

问题分析

我们有 $N$ 个位置不同的砝码，需要找到一个宽度 $w$ 最小的箱子，使得在依次移除最左或最右砝码的过程中，剩余砝码的重心始终落在箱子支撑区间 $[l, l+w]$ 内。

核心思路

这个问题可以通过分析所有可能的子段重心范围，并找到满足条件的最小宽度。

关键观察

1. 重心范围：对于每个可能的剩余砝码数量 $k$，重心必须在某个范围内
2. 单调性：随着移除砝码，重心会发生变化，但必须始终在支撑区间内
3. 最小宽度：支撑区间的宽度 $w$ 必须覆盖所有阶段的重心变化范围

算法详解

1. 预处理前缀和

for (int i = 1; i <= n; i++)
    pre[i] = pre[i - 1] + A[i];

计算前缀和以便快速计算任意子段的和。

2. 计算所有可能子段的重心

double Mid = 1.*pre[n] / n;  // 所有砝码的重心

for (int len = 1; len < n; len++) {
    // 二分找到重心最接近Mid的子段
    int lt = 0, rt = (n - len + 1) + 1;
    while (lt + 1 < rt) {
        int mid = lt + rt >> 1;
        if (1.*(pre[mid + len - 1] - pre[mid - 1]) / len < Mid) {
            lt = mid;
        } else {
            rt = mid;
        }
    }
    
    // 收集重心值
    if (!lt) lt++;
    int tot = 2;
    while (lt + len - 1 <= n && tot--) {
        int rt = lt + len - 1;
        need.push_back(make_pair(len, 1.*(pre[rt] - pre[lt - 1]) / len));
        lt++;
    }
}
need.push_back(make_pair(n, Mid));  // 加入初始状态

这部分的作用：

• 对于每个可能的剩余砝码数量 $len$，找到重心最接近整体重心 $Mid$ 的子段
• 只保留最接近的2个子段以减少计算量
• 按重心值排序后处理

3. 使用优先队列跟踪最小重心

class ddd {
public:
    priority_queue<double> A, D;  // 主堆和删除堆
    void push(double x) { A.push(-x); }
    void del(double x) { D.push(-x); }
    double top() {
        while (D.size() && (fabs(A.top() - D.top()) < eps))
            A.pop(), D.pop();
        return -A.top();
    }
} q;

// 初始化
for (int i = 1; i <= n; i++) {
    neta[i] = -1e9;
    q.push(neta[i]);
}

// 处理每个重心值
double ans = 1e9;
for (int i = 0; i < need.size(); i++) {
    q.del(neta[need[i].first]);
    neta[need[i].first] = need[i].second;
    q.push(neta[need[i].first]);
    ans = min(ans, need[i].second - q.top());
}

这部分的作用：

• 维护一个可以删除元素的优先队列
• 对于每个重心值，更新对应长度 $len$ 的最大重心
• 计算当前重心值与所有长度中最小重心的差值，更新答案

算法正确性分析

为什么这样能找到最小宽度？

1. 支撑区间必须覆盖：对于每个阶段（剩余 $k$ 个砝码），支撑区间必须包含该阶段的重心
2. 最紧约束：最小宽度由某个阶段的最大重心和另一个阶段的最小重心之差决定
3. 排序处理：通过按重心值排序，可以确保在遍历过程中，当前重心是所有已处理重心中最大的，而队列顶部是当前所有长度中的最小重心

时间复杂度

• 预处理：$O(n \log n)$（二分查找）
• 排序：$O(n \log n)$
• 优先队列操作：$O(n \log n)$
• 总复杂度：$O(n \log n)$，满足 $n \leq 2\times 10^5$ 的要求

样例验证

样例1：

• 所有砝码重心：$(1+2+4)/3 = 7/3$
• 关键子段重心：长度为2时最接近7/3的子段是[1,2]和[2,4]
• 计算得到最小宽度 $5/6$

样例2：

• 类似分析得到最小宽度 $1.166666667$

总结

本题的巧妙之处在于：

1. 将物理平衡问题转化为数学上的区间覆盖问题
2. 通过分析所有可能子段的重心，找到必须覆盖的范围
3. 使用数据结构高效计算最小宽度

这种"枚举所有可能状态 + 数据结构优化"的思路在竞赛中很常见，关键是找到问题的本质特征并设计合适的数据结构。