尺取法

• Codeforces 中显示显示它的算法名称叫做“two pointers”
• 直译成中文的话就叫双指针法
• 通常是指对数组保存一对下标（起点、终点），然后根据实际情况交替推进两个端点来计算答案。
  这种操作很像日本尺取虫的爬行方式，所以叫做尺取法
• 一般用来解决具有单调性的区间问题，很多题目都要用到尺取法来辅助或优化计算

UVA1121 Subsequence

有一个长度为 $N$ 的正整数序列 $(10 < N < 100,000)$，每一个数字都小于等于 $10000$，再给定一个正整数 $S (S < 100,000,000)$，试求一个连续子序列，使得该序列的数字之和大于或等于 $S$，并且要求该子序列尽量短。

考虑子序列 $[l, r)$，我们设从 $a_l$ 开始总和最初大于等于 $S$ 的连续子序列为 $a_l + a_{l + 1} + \cdots + a_{r - 1}$ ，此时有

$$ a_{l + 1} + \cdots + a_{r - 2} < a_l + \cdots + a_{r - 2} < S $$

所以从 $a_{l + 1}$ 开始总和最初至少为 $S$ 的连续子序列如果是 $a_{l + 1} + \cdots + a_{p - 1}$ 的话，则必然有 $r \leqslant p$

利用上述性质可以设计出如下算法：

1. 以 $l = r = sum = 0$ 初始化
2. 只要有 $sum < S$，就不断的将 $sum$ 加 $a_t$，并且 $r++$
3. 如果 (2) 中无法满足 $sum >= S$ 就终止，否则的话，更新 $res = \min(res, r - l)$
4. 将 $sum$ 减去 $a_l$，$r$ 增加 $1$，回到 (2)

对于这个算法，因为 $r$ 最多变化 $n$ 次，所以复杂度是 $O(n)$

Code:

#include <bits/stdc++.h>
#define rep(i, n) for (int i = 0; i < (n); ++i)

using std::cin;
using std::cout;
using std::min;
using std::vector;

int main() {
    int n, s;

    while (cin >> n >> s) {
        vector<int> a(n);
        rep(i, n) cin >> a[i];
        int l = 0, r = 0, sum = 0;
        int ans = n + 1;
        while (true) {
            while (r < n and sum < s) {
                sum += a[r++];
            }
            if (sum < s) break;
            ans = min(ans, r - l);
            sum -= a[l++];
        }
        cout << (ans == n + 1 ? 0 : ans) << '\n';
    }

    return 0;
}

一些练习题

1. Xor Sum 2
2. Petya and Array
3. Longest X