chail's Blog
博客 分类 标签
chail's Blog

目录

目录

[蓝桥杯 2026 省 B] 理想温度 题解

 收录于  类别 算法足迹
     约 1562 字   预计阅读 7 分钟 

[蓝桥杯 2026 省 B] 理想温度 题解

本人昨天刚刚参加今年的蓝桥杯，是第一次参加校级以上的算法赛事了。

到达浙理工，我发现这里室内好暗好封闭，尤其是他们的机房，让我有一种不舒服的感觉。

比赛即将开始，发现环境还要自己配置，包括安装监考系统，连接考试服务器等。他们把服务器地址写在前面白板上，我们这帮天天坐在电脑前敲代码的人怎么可能看得清！无奈只能多次下位前去查看。总之挺闹心的。

赛时发挥还行，至少早早放弃了不会的第二题…不过很坑爹的一点是PDF题面，当你复制它的样例时就能发现会吞掉几个空格！害得我在第四题多花了不少时间。

这道题是倒数第二题，赛时头脑风暴想到了哈希表记录差值，前缀和记录0数量的O(n)解法，但是没有处理好中间有很多0的情况！大概是顶多拿一半分了。于是便来写题解弥补遗憾。

P16238 [蓝桥杯 2026 省 B] 理想温度

一条工业流水线上排列着 n 个温度传感器。当前各个传感器测得的温度记录在数组 A 中，而各传感器对应的理想标准温度记录在数组 B 中（即 Ai 为第 i 个传感器的当前温度，Bi 为第 i 个传感器的理想温度）。

为了让尽可能多的传感器达到理想温度，你可以进行一次区域温度补偿操作：

  1. 在流水线上划定一段连续的传感器区间 $[l, r]（即第（即第l个到第个到第r$ 个传感器）。
  2. 输入一个温度补偿值 k（k 为任意整数），使得该区间内所有传感器的当前温度都加上 k。

请问在执行完这一次校准操作后，最多能使多少个传感器的温度恰好等于其对应的理想标准温度？

第一行包含一个整数 n，表示传感器的数量。

第二行包含 n 个整数 A1,A2,…,An，表示各传感器的当前温度。

第三行包含 n 个整数 B1,B2,…,Bn，表示各传感器对应的理想标准温度。

输出一行，包含一个整数，表示补偿操作后处于理想温度的传感器最大数量。

5
1 2 3 4 5
2 3 2 3 2
2

对于 $30%$ 的评测用例，保证 $1 \le n \le 2000$；

对于所有评测用例，保证 $1 \le n \le 2 \times 10^5$, $-10^9 \le A_i, B_i \le 10^9$。

我们很容易就能想到，我们只关心两个数组的差值，差值为 $0$ 的就是理想温度。所以先把差值数组处理出来。我们需要做一次区间加减操作使得最后的差值数组中的 $0$ 数量最多。可以知道答案至少是操作前 $0$ 的数量。

先处理出差值数组 $a$ 与 $0$ 的数量前缀和 $cntz$:

for (int i=1;i<=n;++i) cin >> a[i];
    for (int i=1;i<=n;++i) {
        int bi;
        cin >> bi;
        a[i] = bi-a[i];
        if (a[i]==0)cntz[i] = cntz[i-1]+1;
        else cntz[i] = cntz[i-1];
    }

因为我们只能做一次区间操作，所以要找的就是某个同一差值数量与 $0$ 数量的差最大的子段（操作时会破坏 $0$）。由于不同差值的数量最多就只有 $n$ 个，我们可以用哈希表来维护每一个差值 $x$ 的状态。

对于每个差值 x ，我们需要知道它在某个区间的数量 cnt，以及区间的左右边界用于统计区间内 0 的数量。从 1 到 n 遍历差值数组，动态维护哈希表。这里我用一个struct记录：

struct rd {
    int l, r, cnt;
};
unordered_map<int,rd> mp;

对于当前差值 $x$：

  • 如果是 $0$，跳过，不需要处理。
  • 如果是第一次遇到：mp[a[i]] = {i,i,1}
  • 如果不是第一次遇到并且mp[a[i]].cnt+1<=cntz[i]-cntz[mp[a[i]].l-1]。这说明当前差值 $x$ 的这一段对于最终结果没有任何贡献，那么我们就要舍弃这一段，因为把它算上的话在后面也不会有贡献甚至减少后面的贡献，所以重置：mp[a[i]] = {i,i,1}。
  • 如果它的贡献大于$0$，那么增加 $cnt$，扩展右边界即可：mp[a[i]].r=i;mp[a[i]].cnt++;·。

如此我们就可以得到当前的差值的贡献情况，每次更新答案即可：

res = max(res, cntz[n]+mp[a[i]].cnt-(cntz[mp[a[i]].r] - cntz[mp[a[i]].l-1]));

#include <bits/stdc++.h>
#define int long long
using namespace std;
int a[200005];
int cntz[200005] = {0};
struct rd {
    int l, r, cnt;
};
unordered_map<int,rd> mp;
signed main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n;
    cin >> n;
    for (int i=1;i<=n;++i) cin >> a[i];
    for (int i=1;i<=n;++i) {
        int bi;
        cin >> bi;
        a[i] = bi-a[i];
        if (a[i]==0)cntz[i] = cntz[i-1]+1;
        else cntz[i] = cntz[i-1];
    }
    int res = cntz[n];
    for (int i=1;i<=n;++i) {
        if (a[i]==0) continue;
        if (mp.find(a[i])==mp.end()) {
            mp[a[i]] = {i,i,1};
        }
        else {
            if (mp[a[i]].cnt+1<=cntz[i]-cntz[mp[a[i]].l-1]) {
                mp[a[i]] = {i,i,1};
            }
            else {
                mp[a[i]].r=i;
                mp[a[i]].cnt++;
            }
        }
        res = max(res, cntz[n]+mp[a[i]].cnt-(cntz[mp[a[i]].r] - cntz[mp[a[i]].l-1]));
    }
    cout << res << "\n";
    return 0;
}
更新于 2026-04-12
 | 主页