很多序列题看起来都在“枚举一段区间”，但区间的性质不同，最合适的工具也不同：长度固定时维护窗口和，约束单调时移动左右边界，查询阈值时在有序数据上二分。

本文选择三道 Codeforces 官方题目，把它们放在同一条学习路径上。重点不是记住三份代码，而是学会通过题目结构选择数据移动方式。

1. 先判断区间属于哪一种模型

三种方法都在避免重复工作：窗口复用上一次的和，双指针保证边界只向前移动，二分则利用有序性排除一半范围。

2. 363B Fence：固定长度窗口的最小和

官方题目：363B Fence · 难度 1100 · 官方标签：brute force、dp

题意压缩

在一列高度中找到长度恰好为 k 的连续区间，使区间元素和最小，并输出起点。

如果每个起点都重新累加 k 个元素，会重复计算相邻窗口中重合的部分。窗口向右移动一格时，只需要减去离开的元素，再加上新进入的元素。

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
#include <iostream>
#include <vector>
using namespace std;

int main() {
    int count, windowSize;
    cin >> count >> windowSize;

    vector<int> heights(count);
    for (int &height : heights) {
        cin >> height;
    }

    long long currentSum = 0;
    for (int i = 0; i < windowSize; ++i) {
        currentSum += heights[i];
    }

    long long minimumSum = currentSum;
    int bestStart = 0;

    for (int right = windowSize; right < count; ++right) {
        currentSum += heights[right];
        currentSum -= heights[right - windowSize];

        if (currentSum < minimumSum) {
            minimumSum = currentSum;
            bestStart = right - windowSize + 1;
        }
    }

    cout << bestStart + 1;
    return 0;
}

程序内部使用 0 下标，输出时转回题目要求的 1 下标。只在严格更小时更新，可以自然保留最靠左的最优区间。

3. 279B Books：可变长度窗口与双指针

官方题目：279B Books · 难度 1400 · 官方标签包含：two pointers、binary search

题意压缩

每本书需要一定阅读时间，必须从某一本开始连续阅读，在总时间不超过预算的前提下，求最多能读多少本。

这里的区间长度不固定，但所有阅读时间为正，因此具有单调性：右端加入新书只会让总时间增加；一旦超出预算，移动左端会让总时间减小。这正是双指针能够工作的原因。

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
#include <algorithm>
#include <iostream>
#include <vector>
using namespace std;

int main() {
    int bookCount;
    long long timeLimit;
    cin >> bookCount >> timeLimit;

    vector<int> readingTime(bookCount);
    for (int &time : readingTime) {
        cin >> time;
    }

    int left = 0;
    int answer = 0;
    long long windowSum = 0;

    for (int right = 0; right < bookCount; ++right) {
        windowSum += readingTime[right];

        while (windowSum > timeLimit) {
            windowSum -= readingTime[left];
            ++left;
        }

        answer = max(answer, right - left + 1);
    }

    cout << answer;
    return 0;
}

为什么是线性复杂度

代码里有一层 for 和一层 while，但左指针不会回退。每个元素最多被右指针加入一次、被左指针移出一次，所以总移动次数不超过序列长度的常数倍，时间复杂度是 O(n)。

如果元素允许为负数，“右移只会让和增加”就不再成立，这套窗口收缩逻辑也会失效。使用双指针前，先确认维护的量具有单调性。

4. 706B Interesting drink：排序后回答阈值查询

官方题目：706B Interesting drink · 难度 1100 · 官方标签：binary search、implementation

题意压缩

给出一组商品价格，再处理多次独立查询。每个查询给出一个预算，需要统计价格不超过预算的商品数量。

如果每次查询都扫描全部价格，重复工作很多。先把价格排序，对于预算 money，第一个大于它的位置，恰好等于“小于等于预算”的元素数量。

这正是 C++ 标准库 upper_bound 的含义。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
#include <algorithm>
#include <iostream>
#include <vector>
using namespace std;

int main() {
    int shopCount;
    cin >> shopCount;

    vector<int> prices(shopCount);
    for (int &price : prices) {
        cin >> price;
    }
    sort(prices.begin(), prices.end());

    int queryCount;
    cin >> queryCount;
    while (queryCount--) {
        int money;
        cin >> money;
        cout << upper_bound(prices.begin(), prices.end(), money) - prices.begin() << '\n';
    }
    return 0;
}

lower_bound 与 upper_bound 不要凭感觉选

工具 返回的位置 当前位置之前的元素
lower_bound(x) 第一个 >= x 全部 < x
upper_bound(x) 第一个 > x 全部 <= x

题目要统计“不超过预算”，所以使用 upper_bound。遇到“小于”“小于等于”这样的描述时，先写出希望被统计的集合，再选择边界函数。

5. 三种方法的统一视角

题目 数据是否有序 区间长度 复用的信息 复杂度
363B 原顺序 固定 上一个窗口的和 O(n)
279B 原顺序 可变 当前可行窗口与左边界 O(n)
706B 先排序 不要求连续区间 有序位置 O(n log n + q log n)

选择方法时可以依次问：

  1. 是否要求连续；
  2. 长度是否固定；
  3. 窗口扩大后，约束是否单调变化；
  4. 查询之间是否独立；
  5. 是否可以先排序而不破坏题意。

6. 建议的提交与复盘顺序

先完成 363B，确保能正确维护固定窗口；再完成 279B，理解为什么左边界可以单向移动；最后完成 706B，把“计数问题”转化成“查找边界位置”。

每道题通过后，不妨再回答一个反事实问题：如果数据允许负数、如果要求保留原下标、如果查询在线到达，当前方法还成立吗？这些变化能帮助我们真正理解算法依赖的条件。

返回入门篇：Codeforces 入门四题：把题意翻译成判断、计数与模拟。更多题目会继续整理到 算法练习路径。

官方来源