# 122.精华帖子

开辟一个数组，默认都是0，把精华帖标记为1.

使用前缀和，快速计算出，k 范围内有多少个精华帖。

前缀和要特别注意区间问题，即 vec[i+k] - vec[i] 求得区间和是 (i, i + k] 这个区间，注意这是一个左开右闭的区间。

所以前缀和很容易漏掉 vec[0] 这个数值的计算

#include <iostream>
#include <vector>
using namespace std;
int main() {
    int n, m, k, l, r;
    cin >> n >> m >> k;
    vector<int> vec(n);
    while (m--) {
        cin >> l >> r;
        for (int i = l; i < r; i++) vec[i] = 1;
    }
    int result = 0;
    for (int i = 0; i < k; i++) result += vec[i]; // 提前预处理result，包含vec[0]的区间，否则前缀和容易漏掉这个区间

    for (int i = 1; i < n; i++) {
        vec[i] += vec[i - 1];
    }

    for (int i = 0; i < n - k; i++) {
        result = max (result, vec[i + k] - vec[i]);
    }
    cout << result << endl;
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23