L2453. 「POI2010」积木 Blocks 题解

题目大意

给定 $n$ 个正整数 $a_1, a_2, \ldots, a_n$ 和 $m$ 次询问，每次给出一个正整数 $k$。可以进行如下操作：

• 选择一个大于 $k$ 的 $a_i$，将 $a_i$ 减 1，并选择 $a_{i-1}$ 或 $a_{i+1}$ 加 1

问经过若干次操作后，能够得到的最长连续子序列的长度，使得该子序列中每个数都不小于 $k$。

解题思路

关键观察

1. 操作的本质：操作允许将数值从大于 $k$ 的位置"移动"到相邻位置，这相当于重新分配数值，但保持总和不变。

2. 必要条件：如果一个长度为 $L$ 的连续子序列能够通过操作使得每个数都不小于 $k$，那么这个子序列的平均值必须至少为 $k$。

3. 充分性：实际上，只要一个连续子序列的平均值不小于 $k$，就一定能通过操作使得该子序列中每个数都不小于 $k$。

问题转化

对于每个询问 $k$，我们需要找到最长的连续子序列 $[i,j]$，使得：

等价于：

算法设计

1. 前缀和数组：定义 $sum[i] = \sum_{t=1}^i (a_t - k)$

2. 关键性质：对于区间 $[i,j]$，有 $\sum_{t=i}^j (a_t - k) = sum[j] - sum[i-1]$

3. 问题进一步转化：我们需要找到最大的 $j-i$，使得 $sum[j] \geq sum[i-1]$

4. 单调栈优化：

   • 从左到右构建单调栈，存储可能成为"左端点"的位置
   • 从右到左扫描，对于每个位置 $j$，在栈中寻找满足 $sum[i] \leq sum[j]$ 的最小 $i$

时间复杂度

• 预处理：$O(n)$
• 每次询问：$O(n)$
• 总复杂度：$O(n \cdot m)$，在给定数据范围内可行

代码实现

#include <bits/stdc++.h>
#define int long long
using namespace std;

int n, a[1000001], m;
int sum[1000001];
stack<int> st;

signed main() {
    ios::sync_with_stdio(0);
    cin.tie(nullptr);
    cin >> n >> m;

    for (int i = 1; i <= n; i++)
        cin >> a[i];

    while (m--) {
        int k, ans = 0;
        cin >> k;

        // 计算前缀和
        for (int i = 1; i <= n; i++) {
            sum[i] = sum[i - 1] + a[i] - k;

            // 如果前缀和非负，整个前缀都是可行解
            if (sum[i] >= 0)
                ans = max(ans, i);

            // 维护单调递减栈
            if (st.empty() || sum[st.top()] > sum[i])
                st.push(i);
        }

        // 从右向左扫描，寻找最大区间
        for (int i = n; i >= 1; i--) {
            while (!st.empty() && sum[st.top()] <= sum[i]) {
                ans = max(ans, i - st.top());
                st.pop();
            }
        }

        // 清空栈以备下次使用
        while (!st.empty()) st.pop();
        
        cout << ans << ' ';
    }

    cout << '\n';
    return 0;
}

算法流程详解

1. 对于每个询问 $k$：

   • 计算前缀和数组 $sum[i] = \sum_{t=1}^i (a_t - k)$
   • 构建单调栈，存储可能成为最优左端点的位置

2. 单调栈构建原则：

   • 如果当前 $sum[i]$ 小于栈顶元素对应的前缀和，则入栈
   • 这保证了栈中元素的前缀和是单调递减的

3. 从右向左扫描：

   • 对于每个位置 $j$，弹出所有满足 $sum[st.top()] \leq sum[j]$ 的栈顶元素
   • 这意味着对于这些栈顶位置 $i$，区间 $[i+1, j]$ 的和非负
   • 更新最大长度 $ans = \max(ans, j - st.top())$

示例分析

对于样例：

n=5, a=[1,2,1,1,5]
k=1,2,3,4,5,6

当 $k=1$ 时：

• 前缀和：$[0,1,2,2,2,6]$
• 可以找到整个序列都满足条件，答案为 5

当 $k=3$ 时：

• 前缀和：$[-2,-1,-1,-2,0]$
• 最长满足条件的子序列长度为 2

总结

本题的关键在于将操作可行性问题转化为平均值问题，进而转化为前缀和比较问题。通过单调栈优化，我们能够在 $O(n)$ 时间内解决每个询问，整体复杂度 $O(nm)$ 在给定约束下是可接受的。

这种将操作问题转化为数学条件，再通过数据结构优化的思路，在竞赛中十分常见，值得深入学习掌握。