题解：P13734 [JOIGST 2025] 雪球 2 / Snowball 2

· · 题解

妥妥的分治题。

题目描述：

Aoi 面前有 N 个雪球从左到右排成一列，每个雪球有一个大小。她希望将这些雪球最终合并成一个大雪球。

合并规则是：

每次可以选择两个相邻的雪球，左边的大小为 l，右边的大小为 r，要求满足 0 ≤ l - r ≤ 1，然后将它们合并成一个大小为 l + r 的新雪球。

这个操作可以重复进行，直到只剩一个雪球或者无法继续操作。问是否可能通过一系列操作将所有雪球合并成一个。

题目分析：

仔细读题，不难发现只有当左边的雪球不小于右边，并且差值不超过 1 时才能合并。所以合并过程对顺序和数值大小非常敏感。

我们考虑贪心。从左到右或从右到左不断合并，可能会因为局部最优选择而破坏全局合并的可能性。

分析一下样例，可以发现，比如三个大小为 2 的雪球无法合并，因为无论怎么合并都会导致差值超过 1。

而五个大小为 1 的雪球可以成功合并，说明初始值的大小和合并顺序都至关重要。

观察发现，最终的合并过程可以看作是一棵二叉树，每次合并对应一个内部节点。

整个序列被分成左右两部分，分别合并成一个雪球，然后再合并这两个结果。这马上就能想到分治。

要能最终合并，必须存在一个分割点，使得左半部分和右半部分都能独立合并成功，并且它们的总和满足合并条件。

题目解答：

基于刚刚的观察，我们可以考虑采用分治加二分搜索的策略。

定义一个函数 merge(l, r) 表示区间 [l, r] 是否可以合并成一个雪球。

关键优化在于，我们利用合并条件推导出左半部分的总和必须接近整个区间总和的一半。

具体来说，设总和为 total，左半部分和为 s1，右半部分和为 s2，必须满足 s1 ≥ s2 且 s1 - s2 ≤ 1。通过推导可得 s1 必须等于 (total + 1) ÷ 2。

因此，我们可以用前缀和数组快速计算区间和，并通过二分查找找到满足左半部分和等于 (total + 1) ÷ 2 的 mid 位置。

然后递归检查左右两部分是否都能成功合并。

我们可以使用 map 记忆化已经计算过的区间结果。

在函数内部，先检查边界和记忆化缓存。设 mid 表示中间位置，然后计算目标左半部分和，用二分查找可能的 mid 位置，并检查 mid 附近几个位置是否满足条件。

如果能找到一个可行的分割点，返回 true，否则返回 false 就行了。

代码：

#include<bits/stdc++.h>
using namespace std;
int n;
long long a[500005], pre[500005]; // a数组存储输入的雪球大小，pre为前缀和数组
map<pair<int, int>, bool> mp;     // 记忆化搜索的缓存，避免重复计算相同区间
// 函数：判断区间 [l, r] 是否可以合并成一个雪球
bool merge(int l, int r) {
    // 如果区间只有一个元素，直接返回 true
    if (l == r) 
        return true;
    // 创建当前区间的键值对，用于记忆化
    pair<int, int> key = {l, r};
    // 如果该区间已经计算过，直接返回缓存结果
    if (mp.find(key) != mp.end()) 
        return mp[key];
    // 计算区间 [l, r] 的总和
    long long total = pre[r] - pre[l-1];
    // 根据合并条件推导：左半部分的和 s1 必须满足 s1 >= s2 且 s1 - s2 <= 1
    // 其中 s2 = total - s1，解得 s1 的理论值
    long long s1_low = (total + 1) / 2;  
    long long s1_high = (total + 1) / 2; 
    // 目标左半部分的和
    long long t_sum = s1_low;
    // 对应的目标前缀和值
    long long t_pre = pre[l-1] + t_sum;
    // 二分查找：在 [l, r-1] 范围内寻找 pre[mid] == t_pre 的位置
    int L = l, R = r - 1;
    int mid = -1;
    while (L <= R) {
        int mid_idx = (L + R) / 2;
        if (pre[mid_idx] == t_pre) {
            mid = mid_idx;  // 找到目标位置
            break;
        } 
        else if (pre[mid_idx] < t_pre) {
            L = mid_idx + 1;  // 在右半部分继续查找
        } 
        else {
            R = mid_idx - 1;  // 在左半部分继续查找
        }
    }
    // 如果找到了一个可能的分割点 mid
    if (mid != -1) {
        int mid_s = mid;
        // 递归检查左右两部分是否都能合并成功
        if (merge(l, mid_s) && merge(mid_s + 1, r)) 
            return mp[key] = true;  // 如果可以，缓存并返回 true
    }
    // 为了防止浮点或整数边界问题，尝试 mid 附近的位置（-1, 0, +1）
    for (int i = -1; i <= 1; i++) {
        int mid_s = mid + i;
        // 检查 mid_s 是否在有效范围内
        if (mid_s < l || mid_s >= r) 
            continue;
        // 计算左右两部分的实际和
        long long s1 = pre[mid_s] - pre[l-1];
        long long s2 = pre[r] - pre[mid_s];
        // 检查是否满足合并条件：左 >= 右 且 差值 <= 1
        if (s1 >= s2 && s1 - s2 <= 1) 
            // 递归检查两部分是否可合并
            if (merge(l, mid_s) && merge(mid_s + 1, r)) 
                return mp[key] = true;  // 成功则缓存并返回
    }
    // 所有尝试都失败，缓存并返回 false
    return mp[key] = false;
}
int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    cin >> n;
    // 读入雪球大小，并计算前缀和
    for (int i = 1; i <= n; i++) {
        cin >> a[i];
        pre[i] = pre[i-1] + a[i];
    }
    // 调用 merge 函数判断整个区间 [1, n] 是否可合并
    if (merge(1, n)) 
        cout << "Yes\n";
    else 
        cout << "No\n";

    return 0;
}