【每日一题】Problem 602B. Approximating a Constant Range

原题

解决思路

设 \([a_l, a_r]\) 满足要求，而加入 \(a_{r+1}\) 则不满足要求，那么根据题目中相邻两数差不超过 1，\(a_{r+1} - min([a_l, a_r]) = 2\quad or\quad max([a_l, a_r]) - a_{r+1}\) 成立。当有多个 \(a_i = (min([a_l, a_r])\quad or\quad max([a_l, a_r]))\) 时，取最右边的，过程如下图所示

那么，我们只需用 map 来记录每个数字最后出现的为止即可，代码如下

#include <bits/stdc++.h>

int main() {
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);
    int n; std::cin >> n;
    std::vector<int> vec(n, 0);
    for (int i = 0; i < n; ++i) std::cin >> vec[i];

    std::map<int, int> m;
    int cnt, ans; cnt = ans = 0;
    for (int i = 0; i < n; ++i) {
        int minV = vec[i] - 2;
        int maxV = vec[i] + 2;
        if (m.find(maxV) != m.end()) {
            cnt = i - m[maxV] - 1;
            m.erase(maxV);
        }
        if (m.find(minV) != m.end()) {
            cnt = std::min(cnt, i - m[minV] - 1);
            m.erase(minV);
        }
        m[vec[i]] = i;
        ++cnt;
        ans = std::max(ans, cnt);
    }

    std::cout << ans << "\n";

    return 0;
}

误区

1. \(cnt\) 应取大-小和小-大中的最小值
2. 需要将 \(a_l\) 的值从 map 中删除，因为 \(a_l\) 必定是加入 \(a_{r+1}\) 后的子数组中最大的值或最小的值，不满足新数组的要求，因此应删除该值