我的算法书 - Bound Found

https://vjudge.net/problem/POJ-2566#author=DeepSeek_zh

这是一道非常经典的算法题目（对应 POJ 2566 - Bound Found）。

针对你的核心疑问：“数组中有负数，打破了普通滑动窗口的单调性，如何使用双指针？”

答案是：不要直接在原数组上跑双指针，而是在“排序后的前缀和数组”上跑双指针。

核心解题思路

1. 转换问题：前缀和 (Prefix Sum)

原数组 $A$ 中含有负数，导致区间伸缩时和的大小变化不可预测。但是，任何一个子区间 $[l, r]$ 的和都可以表示为两个前缀和的差：

Sum(l, r) = P[r] - P[l-1]

其中

P[i]

是前

i

个元素的和，

P[0] = 0

。

题目要求找到 $|Sum(l, r)| \approx t$ ，等价于找到两个前缀和 $P[x]$ 和 $P[y]$ ，使得：

|P[x] - P[y]| \approx t

问题就转变成了在一个单调数组上,查找最 $A-B \approx C$ 的数值.

2. 制造单调性：排序 (Sorting)

虽然原数组有负数导致前缀和数组 $P$ 也是乱序的，但如果我们把 $P$ 数组按照数值大小从小到大排序，情况就变了。

设排序后的前缀和数组为 $S$ 。此时 $S$ 是单调递增的。对于 $S$ 中的任意两个元素 $S[right]$ 和 $S[left]$ （其中 $right > left$ ），它们的差 $diff = S[right] - S[left]$ 必定是 非负的。

这就构造出了双指针所需的单调性：

如果 $diff < t$ ：我们需要更大的差值，所以 右指针 right 向右移（找一个更大的数减去当前的左边）。
如果 $diff > t$ ：差值太大了，我们需要更小的差值，所以 左指针 left 向右移（找一个更大的被减数，缩短两者距离）。

3. 算法流程

计算前缀和：生成包含 $(N+1)$ 个元素的数组（包含初始的0），存储结构为 {value, original_index}。
排序：按照 value 对前缀和数组进行升序排序。
双指针扫描：
- 初始化 left = 0, right = 1。
- 计算 diff = S[right].val - S[left].val。
- 检查 diff 与目标 t 的接近程度，更新全局最优解（记录最小差值、以及对应的原始下标）。
- 移动指针：
  - 若 diff < t：right++。
  - 若 diff > t：left++。
  - 若 diff == t：直接找到完美解，跳出。
  - 注意：若 left == right，强制 right++ 以保持区间非空。

4. 还原下标

排序打乱了原始下标，但我们在结构体里保存了 original_index。假设找到的最优对是 $S[left]$ 和 $S[right]$ ，它们的原始下标分别是 $id_1$ 和 $id_2$ 。

区间起点 $l = \min(id_1, id_2) + 1$
区间终点 $u = \max(id_1, id_2)$

C++ 代码实现

cpp

copy

        1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96

        #include <iostream>
#include <algorithm>
#include <cmath>

using namespace std;
typedef long long ll;

const int N = 100005; // 题目范围 1e5，稍微开大一点
const ll INF = 1e18;  // 足够大的初始值
int n, k;

struct Node {
    ll val;
    int id;
    // 重载小于号，sort 时自动调用
    bool operator<(const Node &other) const {
        return val < other.val;
    }
} p[N]; // 全局大数组

ll _abs(ll t) { return t < 0 ? -t : t;}

void work(ll t) {
    // 初始化答案状态
    ll min_gap = INF;
    ll ans_sum = 0;
    int ans_l = 0, ans_r = 0;

    // 双指针初始化
    int l = 0, r = 1;

    // 4. 双指针扫描单调数组
    // 只要 r 没越界，并且 l 也没越界 (实际上 r 会先触顶)
    while (r <= n && l <= n) {
        ll diff = p[r].val - p[l].val;
        ll gap = _abs(diff - t);

        // 尝试更新最优解
        if (gap < min_gap) {
            min_gap = gap;
            ans_sum = diff;
            ans_l = p[l].id;
            ans_r = p[r].id;
        }

        // 剪枝：如果已经完美匹配，无需继续
        if (gap == 0) break;

        // 移动策略
        if (diff < t) r++;      // 差小了 -> 扩大右边界
        else l++;               // 差大了 -> 扩大左边界

        // 撞车保护：区间长度至少为 1
        if (l == r) r++;
    }

    // 输出结果
    // 题目要求输出区间 [min_id + 1, max_id]
    if (ans_l > ans_r) swap(ans_l, ans_r);
    cout << ans_sum << " " << ans_l + 1 << " " << ans_r << "\n";
}

int main() {
    // 关流加速，竞赛必备
    ios::sync_with_stdio(false);
    cin.tie(0);

    while (cin >> n >> k && (n || k)) {

        // 1. 初始化并构建前缀和
        // p[0] 永远是 0，代表空前缀
        p[0] = {0, 0};

        for (int i = 1; i <= n; ++i) {
            int x;
            cin >> x;
            // 直接利用上一个位置累加，不需要原数组 a[]
            p[i].val = p[i - 1].val + x;
            p[i].id = i;
        }

        // 2. 排序
        // 注意范围是 [0, n]，所以要 sort 到 p + n + 1
        sort(p, p + n + 1);

        // 3. 处理 k 次查询
        while (k--) {
            ll t;
            cin >> t;
            work(t);

        }
    }
    return 0;
}

复杂度分析

前缀和计算: $O(N)$ 。
排序: $O(N \log N)$ 。
查询处理:
- 每次查询使用双指针遍历一次数组，复杂度 $O(N)$ 。
- 总共有 $K$ 次查询。
- 查询总复杂度 $O(K \times N)$ 。
总复杂度: $O(N \log N + K \times N)$ 。
- 鉴于 $N=100,000$ ，如果 $K$ 很大，这可能会超时。但在本题（POJ 2566）的数据范围内， $K$ 比较小，或者测试用例较弱，此解法是标准正解。

总结

这就是处理带负数区间和问题的通解： 前缀和 + 排序 + 双指针。它把原本无序的区间和问题，转化为了有序数组上的两数之差问题。

目录