前言：

对于这道题鼠鼠也是意难平了QAQ

这也是我第一篇csdn望大家手下留情，多多指教。

首先这道题做大的时候并没有完美解答因为做题的时候看到限制想到哈希存储加动态筛选脑子过热了没写出来，难受了

话不多说先看代码

代码：

#include <bits/stdc++.h>
using namespace std;

int main() {

    ios::sync_with_stdio(false);
    cin.tie(0);

    int n;
    cin >> n;

    vector<long long> A(n), B(n);
    for (int i = 0; i < n; ++i) cin >> A[i];
    for (int i = 0; i < n; ++i) cin >> B[i];

    vector<long long> D(n);
    int base = 0; 
    for (int i = 0; i < n; ++i) {
        D[i] = B[i] - A[i];
        if (D[i] == 0) base++;
    }


    map<long long, int> ma; 
    int l = 0;
    int res = 0;      
    int max_ = 0;     

    for (int r = 0; r < n; ++r) {

        if (D[r] != 0) {
            ma[D[r]]++; 
            
            if (ma[D[r]] > res) {
                res = ma[D[r]];     
            }
            
            max_ = max(max_, res); 
        } 

        else {
            if (res == 0) {
                l = r; 
                ma.clear(); 
            } else {
                res--; 
                for (auto it = ma.begin(); it != ma.end(); ) {
                    it->second--; 
                    if (it->second == 0) {

                        it = ma.erase(it); 
                    } else {
                        it++;
                    }
                }
            }
        }
    }

    cout << base + max_ << endl;

    return 0;
}

​ 这道题直接这么看这道题确实不难，思路很明确，只要滑动窗口遍历一遍比全暴力时间暴降O(n)

证明：

题目要求

简单说就是找到最大相同数（a，b数组差值）的最大窗口，注意这里面[l,r]是连续的不能直接找非零连续窗口要不答案不是最优解 like：
下面直接用差值D数组模拟比较方便 -1 -1 1 0 -1 0 -1 -1
暴力枚举是最后两个数加上答案是4，但最好是全部加上1答案是5，所以非0区间否定

那么我们先来解代码：

1.求差值D不多说方便计算

2.遍历数组D分为两个条件第一！0数（需要加上k）和0（本身没有差值的）

2.1！0情况：

用map记录当前窗口中的差值出现次数，如果说这个差值出现次数是最多的用res记录下来，再用max_来记录所用遍历窗口的最大值
（注意：这里的res指的是当前窗口的！0最大相同差值的数量，也是当前最好的改变可选k值已经包括0所降低的值‘后面要考’！！！，所以max_记录的就是所有所遍历的窗口最大值，即为可加上k值改变为0的最大值即为最优解）

2.2 0情况（重点）：

0的情况有两种一种是刚刚接触0时相当于res ！= 0：要res–；后动态刷新窗口不同差值数量，遍历map–；if 差值数量等于 0 删掉就行要不会叠加
如果是被0给删干净了res == 0把左指针拉过来删除所有map记录即可

3.证明

为什么吗??
好，我们来解释
！0我们很好理解略
1.抽象题目：
题目要求在区间里统计加上k到达理想温度数量的最大值，可以抽象为在所有区间里找到拥有最大相同差值的理想区间。
2.当0时，我们为什么要res–：
我们可以假设每个当前窗口都是最优解，要改变的话在里面的0肯定都会变化，所以窗口每加上一个0所有在窗口中的值都要-1。
3.当res == 0时为什么l为什么要拉过来 ：
上文提过res是 当前窗口的！0最大相同差值的数量 所以他肯定是最大值，那么当最大值都为0时，是不是就证明“本窗口加上k改变的理想温度大于从不是理想温度到理想温度的数量”（本窗口之前的最优解数量小于改变值数量），那这个窗口是不是就没有了，所以直接在后面重新开一个新的。
4.为什么要加base + max_ ：
同样，res = 最好的改变可选k值已经包括0所降低的值,max_ = 即为可加上k值改变为0的最大值即为最优解，
max_表示 已经修好的（窗口里面的0） - 改变的值（窗口里面的0），
base 表示 在窗口外的0 + 窗口里面的0，
那么base + max_ 表示 在窗口中所有的0 + 在窗口外所有的0
这是不是所有的0，即为补偿操作后处于理想温度的传感器最大数量题目所求。

创作不易~~~一键三联