当前位置： 首页 > article >正文

差分专题练习 ——基于罗勇军老师的《蓝桥杯算法入门C/C++》

article 2025/3/15 20:55:29

一、1.重新排序 - 蓝桥云课

算法代码：

#include <bits/stdc++.h>
using namespace std;
const int N = 1e5 + 3;

int a[N], d[N], cnt[N];

int main() {
    int n; scanf("%d", &n);
    for (int i = 1; i <= n; i++) scanf("%d", &a[i]);

    int m; scanf("%d", &m);
    long long ans1 = 0, ans2 = 0;

    // 处理区间查询，更新差分数组 d[]
    while (m--) {
        int L, R; scanf("%d%d", &L, &R);
        d[L]++; d[R+1]--;
    }

    // 通过差分数组 d[] 还原累加次数 cnt[]
    cnt[0] = d[0];
    for (int i = 1; i <= n; i++) cnt[i] = cnt[i-1] + d[i];

    // 计算未排序时的累加结果 ans1
    for (int i = 1; i <= n; i++) ans1 += (long long)a[i] * cnt[i];

    // 排序 a[] 和 cnt[]，计算排序后的累加结果 ans2
    sort(a + 1, a + 1 + n);
    sort(cnt + 1, cnt + 1 + n);
    for (int i = 1; i <= n; i++) ans2 += (long long)a[i] * cnt[i];

    // 输出结果
    printf("%lld\n", ans2 - ans1);
    return 0;
}

代码思路解析

1. 问题背景

        这段代码的目标是高效处理多个区间查询，并对数组 a[] 进行累加操作。通过差分数组 d[] 优化区间修改，避免直接遍历区间内的每个元素。

2. 核心思路

  • 差分数组：记录区间修改的起点和终点，避免逐个修改。

  • 前缀和：通过差分数组还原每个位置的累加次数 cnt[]。

  • 排序与匹配：通过排序 a[] 和 cnt[]，计算最小和最大累加结果。

3. 代码实现步骤

  1. 输入数组 a[] 和查询次数 m：

    • 读取数组 a[] 和查询次数 m，初始化差分数组 d[] 和累加次数数组 cnt[]。

  2. 处理区间查询：

    • 对每个查询 [L, R]，更新差分数组 d[]：

      • d[L]++：区间起点加1。

      • d[R+1]--：区间终点外减1（抵消后续影响）。

  3. 还原累加次数 cnt[]：

    • 通过差分数组 d[] 计算每个位置的累加次数 cnt[]：

      • cnt[i] = cnt[i-1] + d[i]。

  4. 计算累加结果：

    • 未排序时：直接计算 ans1 = sum(a[i] * cnt[i])。

    • 排序后：将 a[] 和 cnt[] 排序，计算 ans2 = sum(a[i] * cnt[i])。

  5. 输出结果：

    • 输出排序前后的差值 ans2 - ans1。

4. 复杂度分析

  • 差分数组更新：每个查询 O(1)，总复杂度 O(m)。

  • 累加次数还原：遍历数组 O(n)。

  • 排序：O(nlog⁡n)。

  • 总复杂度：O(m+nlog⁡n)，适用于大规模数据处理。

5. 关键点

  • 差分数组：高效记录区间修改。

  • 前缀和：快速还原累加次数。

  • 排序优化：通过排序匹配最小和最大累加结果。

通过上述思路和代码，可以高效解决区间累加问题。

关于 sort 的排序规则和对应问题

1. sort 的默认行为

  • 默认排序规则：C++ 中的 sort 函数默认是按升序排序的。

  • 排序依据：sort 会根据元素的值进行排序，而不是它们的原始位置。

2. 排序后的对应问题

在代码中，a[] 和 cnt[] 分别被排序：

sort(a + 1, a + 1 + n);      // 对 a[] 排序
sort(cnt + 1, cnt + 1 + n);  // 对 cnt[] 排序

  • 排序后的结果：

    • a[] 和 cnt[] 分别按升序排列。

    • 排序后，a[i] 和 cnt[i] 的对应关系被打破，因为它们各自独立排序。

3. 为什么排序后仍然有效？

  • 目标：代码的目标是计算两种累加结果的差值：

    • 未排序时：ans1 = sum(a[i] * cnt[i])，即原始对应关系下的累加结果。

    • 排序后：ans2 = sum(a[i] * cnt[i])，即排序后的累加结果。

  • 数学原理：

    • 排序后，a[] 和 cnt[] 分别按升序排列，此时 ans2 是 a[] 和 cnt[] 的最小匹配累加结果。

    • 由于 a[] 和 cnt[] 都是升序排列，ans2 是 a[] 和 cnt[] 的最小可能累加和。

    • 差值 ans2 - ans1 反映了排序对累加结果的影响。

4. 排序的意义

  • 未排序时：ans1 是基于原始对应关系的累加结果。

  • 排序后：ans2 是基于最小匹配的累加结果。

  • 差值 ans2 - ans1：

    • 如果 ans2 < ans1，说明排序后的累加结果更小。

    • 如果 ans2 > ans1，说明排序后的累加结果更大。

    • 差值反映了排序对累加结果的影响。

5. 代码的逻辑

  • 未排序时：直接计算原始对应关系下的累加结果 ans1。

  • 排序后：计算最小匹配的累加结果 ans2。

  • 输出差值：ans2 - ans1，反映排序对累加结果的影响。

6. 示例说明

假设：

  • a[] = [3, 1, 2]

  • cnt[] = [2, 3, 1]

未排序时：

  • ans1 = 3*2 + 1*3 + 2*1 = 6 + 3 + 2 = 11

排序后：

  • a[] = [1, 2, 3]

  • cnt[] = [1, 2, 3]

  • ans2 = 1*1 + 2*2 + 3*3 = 1 + 4 + 9 = 14

差值：

  • ans2 - ans1 = 14 - 11 = 3

二、 P1819 - [NewOJ Week 6] 推箱子 - New Online Judge

 算法代码：

#include <bits/stdc++.h>
using namespace std;
typedef long long ll; // 定义 long long 类型别名为 ll，方便使用
const int N = 1e6 + 10; // 定义常量 N 为 1000010，表示数组的最大大小

ll d[N], a[N], sum[N]; // 定义差分数组 d[]，原数组 a[]，前缀和数组 sum[]

int main() {
    int n, h; 
    scanf("%d%d", &n, &h); // 读取障碍物的尺寸 n 和箱子的高度 h

    // 处理每一列的空白区域
    for (int i = 1; i <= n; i++) {
        int li, hi;
        scanf("%d%d", &li, &hi); // 读取第 i 列空白区域的起始位置 li 和结束位置 hi

        // 更新差分数组 d[]
        d[li]++;      // 从第 li 行开始，空白区域的数量增加 1
        d[hi + 1]--;  // 从第 hi+1 行开始，空白区域的影响结束
    }

    // 用差分数组 d[] 计算原数组 a[]
    for (int i = 1; i <= n; i++) {
        a[i] = a[i - 1] + d[i - 1]; // 计算第 i 行的空白数量
    }

    // 用原数组 a[] 计算前缀和数组 sum[]
    for (int i = 1; i <= n; i++) {
        sum[i] = sum[i - 1] + a[i]; // 计算前 i 行的空白数量总和
    }

    // 找到连续 h 行的最大空白数量总和
    ll ans = sum[h - 1]; // 初始化 ans 为前 h 行的空白数量总和
    for (int left = 1; left + h - 1 <= n; left++) {
        // 计算从 left 行开始的连续 h 行的空白数量总和
        ans = max(ans, sum[left + h - 1] - sum[left - 1]);
    }

    // 输出需要清理的障碍物面积
    cout << (ll)n * h - ans << endl; // 总障碍物面积减去最大空白面积
    return 0;
}

代码思路

1. 问题分析

  • 问题描述：在一个高度为 H 的箱子的前方有一个长和高均为 N 的障碍物。每一列有一个连续的空白区域，范围是 [l_i, h_i]。需要找到一条高度为 H 的通道，使得箱子可以直接推出去。输出最少需要清理的障碍物面积。

  • 核心目标：找到连续 H 行的空白区域总和最大的区间，然后用总障碍物面积减去这个最大空白面积，得到需要清理的最小障碍物面积。

2. 解决思路

  • 空白区域的表示：每一列的空白区域 [l_i, h_i] 会影响多行的空白数量。

  • 差分数组优化：使用差分数组 d[] 来高效记录每一列空白区域对行的贡献。

  • 前缀和优化：通过前缀和数组 sum[] 快速计算任意区间的空白数量总和。

  • 滑动窗口：遍历所有可能的连续 H 行区间，找到空白数量总和最大的区间。

代码逻辑流程

1. 初始化

  • 定义常量 N 为 1000010，表示数组的最大大小。

  • 定义 long long 类型的别名 ll，用于处理大整数。

  • 定义差分数组 d[]、原数组 a[] 和前缀和数组 sum[]。

2. 输入处理

  • 读取障碍物的尺寸 n 和箱子的高度 h。

  • 循环读取每一列的空白区域 [l_i, h_i]，并更新差分数组 d[]：

    • d[l_i]++：从第 l_i 行开始，空白区域的数量增加 1。

    • d[h_i + 1]--：从第 h_i + 1 行开始，空白区域的影响结束。

3. 计算原数组 a[]

  • 通过差分数组 d[] 计算原数组 a[]，表示每一行的空白数量：

    • a[i] = a[i - 1] + d[i - 1]。

4. 计算前缀和数组 sum[]

  • 通过原数组 a[] 计算前缀和数组 sum[]，表示前 i 行的空白数量总和：

    • sum[i] = sum[i - 1] + a[i]。

5. 找到最大空白区域

  • 初始化 ans 为前 h 行的空白数量总和。

  • 使用滑动窗口遍历所有可能的连续 h 行区间，找到空白数量总和最大的区间：

    • ans = max(ans, sum[left + h - 1] - sum[left - 1])。

6. 输出结果

  • 计算需要清理的障碍物面积：总障碍物面积 - 最大空白面积。

  • 输出结果：cout << (ll)n * h - ans << endl;。

代码逻辑总结

  1. 输入处理：

    • 读取障碍物的尺寸 n 和箱子的高度 h。

    • 读取每一列的空白区域 [l_i, h_i]，并更新差分数组 d[]。

  2. 差分数组还原：

    • 通过差分数组 d[] 计算原数组 a[]，表示每一行的空白数量。

  3. 前缀和计算：

    • 通过原数组 a[] 计算前缀和数组 sum[]，表示前 i 行的空白数量总和。

  4. 滑动窗口查找最大空白区域：

    • 遍历所有可能的连续 h 行区间，找到空白数量总和最大的区间。

  5. 输出结果：

    • 计算并输出需要清理的最小障碍物面积。

代码优化点

  • 差分数组：将区间更新操作从 O(NH) 优化到 O(N)。

  • 前缀和数组：将区间查询操作从 O(NH) 优化到 O(N)。

  • 滑动窗口：通过滑动窗口遍历所有可能的连续 h 行区间，时间复杂度为 O(N)。

代码适用场景

  • 适用于处理大规模数据（n 和 h 最大为 1000000）。

  • 通过差分数组和前缀和优化，能够高效解决区间更新和查询问题。

通过以上思路和逻辑，代码能够高效地解决推箱子问题，找到需要清理的最小障碍物面积。

三、 1.棋盘 - 蓝桥云课

算法代码： 

#include <bits/stdc++.h>
using namespace std;
const int N=2200;
int a[N][N],d[N][N];
int n,m;

void insert(int x1,int y1,int x2,int y2)
{
    d[x1][y1]++;
    d[x1][y2+1]--;
    d[x2+1][y1]--;
    d[x2+1][y2+1]++;
}

int main()
{
    cin>>n>>m;
    while(m--)
    {
        int x1,y1,x2,y2;
        cin>>x1>>y1>>x2>>y2;
        insert(x1,y1,x2,y2);
    }

    for(int i=1;i<=n;i++)
    {
        for(int j=1;j<=n;j++)
        {
            a[i][j]=d[i][j]+a[i-1][j]+a[i][j-1]-a[i-1][j-1];
            cout<<(a[i][j]&1);
        }
        cout<<endl;
    }
    return 0;
}

代码思路

1. 问题分析

  • 问题描述：给定一个 n x n 的矩阵，初始时所有元素为 0。进行 m 次操作，每次操作将一个子矩阵 [x1, y1] 到 [x2, y2] 内的所有元素加 1。最后输出每个元素的值是否为奇数（1 表示奇数，0 表示偶数）。

  • 核心目标：高效处理多次区间更新操作，并快速查询每个元素的值。

2. 解决思路

  • 二维差分数组：使用二维差分数组 d[][] 来高效记录每次区间更新操作。

  • 前缀和还原：通过二维前缀和还原原数组 a[][]，表示每个元素的值。

  • 奇偶性判断：输出每个元素的值是否为奇数。

代码逻辑流程

1. 初始化

  • 定义常量 N 为 2200，表示矩阵的最大大小。

  • 定义原数组 a[][] 和差分数组 d[][]。

2. 插入操作函数 insert

  • 定义函数 insert(x1, y1, x2, y2)，用于更新差分数组 d[][]：

    • d[x1][y1]++：表示从 (x1, y1) 开始的区域增加 1。

    • d[x1][y2 + 1]--：表示从 (x1, y2 + 1) 开始的区域减少 1。

    • d[x2 + 1][y1]--：表示从 (x2 + 1, y1) 开始的区域减少 1。

    • d[x2 + 1][y2 + 1]++：表示从 (x2 + 1, y2 + 1) 开始的区域增加 1。

3. 主函数

  • 读取矩阵的大小 n 和操作次数 m。

  • 循环处理每次操作：

    • 读取子矩阵的范围 [x1, y1] 到 [x2, y2]。

    • 调用 insert(x1, y1, x2, y2) 更新差分数组 d[][]。

4. 还原原数组 a[][]

  • 使用二维前缀和还原原数组 a[][]：

    • a[i][j] = d[i][j] + a[i - 1][j] + a[i][j - 1] - a[i - 1][j - 1]。

    • 这表示 (i, j) 位置的值等于差分数组的值加上左边和上边的值，减去左上角的值。

5. 输出结果

  • 遍历矩阵的每个元素，输出其值是否为奇数：

    • a[i][j] & 1：判断 a[i][j] 的最低位是否为 1（奇数）。

代码逻辑总结

  1. 初始化：

    • 定义矩阵大小 n 和操作次数 m。

    • 定义原数组 a[][] 和差分数组 d[][]。

  2. 插入操作：

    • 每次操作调用 insert(x1, y1, x2, y2)，更新差分数组 d[][]。

  3. 还原原数组：

    • 使用二维前缀和还原原数组 a[][]。

  4. 输出结果：

    • 遍历矩阵的每个元素，输出其值是否为奇数。

代码优化点

  • 二维差分数组：将区间更新操作从 O(N^2) 优化到 O(1)。

  • 二维前缀和：将区间查询操作从 O(N^2) 优化到 O(1)。

  • 奇偶性判断：通过位运算快速判断每个元素的值是否为奇数。

代码适用场景

  • 适用于处理大规模矩阵的多次区间更新操作。

  • 通过二维差分数组和前缀和优化，能够高效解决区间更新和查询问题。

代码示例

输入

4 2
1 1 2 2
2 2 3 3

输出

1 1 0 0
1 0 1 0
0 1 1 0
0 0 0 0

解释

  • 第一次操作将子矩阵 [1, 1] 到 [2, 2] 内的所有元素加 1。

  • 第二次操作将子矩阵 [2, 2] 到 [3, 3] 内的所有元素加 1。

  • 最终输出每个元素的值是否为奇数。

通过以上思路和逻辑，代码能够高效地处理多次区间更新操作，并快速查询每个元素的值是否为奇数。

重点：

        还原数组 a[][] 的方式是基于 二维前缀和 的原理。需要从 差分数组 和 前缀和 的基本概念入手，逐步推导这个公式。

1. 差分数组的作用

差分数组 d[][] 的作用是高效记录区间更新操作。对于二维数组，差分数组的更新规则如下：

  • 对于一个子矩阵 [x1, y1] 到 [x2, y2] 的区间加 1 操作，这些更新操作的作用是：

  • d[x1][y1]++：表示从 (x1, y1) 开始的区域增加 1。

  • d[x1][y2 + 1]--：表示从 (x1, y2 + 1) 开始的区域减少 1。

  • d[x2 + 1][y1]--：表示从 (x2 + 1, y1) 开始的区域减少 1。

  • d[x2 + 1][y2 + 1]++：表示从 (x2 + 1, y2 + 1) 开始的区域增加 1。

通过这些操作，差分数组 d[][] 记录了每个位置的增量。

2. 前缀和的作用

前缀和的作用是通过累加差分数组 d[][] 来还原原数组 a[][]。对于二维数组，前缀和的计算公式为：

a[i][j]=d[i][j]+a[i−1][j]+a[i][j−1]−a[i−1][j−1]

这个公式的含义是：

  • a[i][j] 表示 (i, j) 位置的值。

  • d[i][j] 是 (i, j) 位置的增量。

  • a[i - 1][j] 是 (i - 1, j) 位置的值，表示上方的前缀和。

  • a[i][j - 1] 是 (i, j - 1) 位置的值，表示左方的前缀和。

  • a[i - 1][j - 1] 是 (i - 1, j - 1) 位置的值，表示左上角的前缀和。

通过这个公式，我们可以将差分数组 d[][] 的增量信息累加到原数组 a[][] 中。

3. 公式的推导

为什么这个公式是正确的？我们可以从 容斥原理 的角度来理解。

  • 目标：计算 (i, j) 位置的值 a[i][j]。

  • 增量来源：

    • d[i][j]：直接贡献给 (i, j) 的增量。

    • a[i - 1][j]：上方的前缀和，包含了 (i - 1, j) 及其左侧的所有增量。

    • a[i][j - 1]：左方的前缀和，包含了 (i, j - 1) 及其上方的所有增量。

    • a[i - 1][j - 1]：左上角的前缀和，被 a[i - 1][j] 和 a[i][j - 1] 重复计算了，需要减去。

因此，公式可以理解为：

a[i][j]=直接增量+上方前缀和+左方前缀和−左上角前缀和a[i][j]=直接增量+上方前缀和+左方前缀和−左上角前缀和

4. 举例说明

假设有一个 3x3 的矩阵，初始时所有元素为 0。我们进行一次区间加 1 操作，范围为 [1, 1] 到 [2, 2]。

更新差分数组

  • d[1][1]++

  • d[1][3]--

  • d[3][1]--

  • d[3][3]++

差分数组 d[][] 的值如下：

d[1][1] = 1
d[1][3] = -1
d[3][1] = -1
d[3][3] = 1

还原原数组

通过前缀和公式计算 a[][]：

  • a[1][1] = d[1][1] + a[0][1] + a[1][0] - a[0][0] = 1 + 0 + 0 - 0 = 1

  • a[1][2] = d[1][2] + a[0][2] + a[1][1] - a[0][1] = 0 + 0 + 1 - 0 = 1

  • a[2][1] = d[2][1] + a[1][1] + a[2][0] - a[1][0] = 0 + 1 + 0 - 0 = 1

  • a[2][2] = d[2][2] + a[1][2] + a[2][1] - a[1][1] = 0 + 1 + 1 - 1 = 1

最终原数组 a[][] 的值如下：

1 1 0
1 1 0
0 0 0

5. 总结

还原数组 a[][] 的公式：

a[i][j]=d[i][j]+a[i−1][j]+a[i][j−1]−a[i−1][j−1]

是基于 二维前缀和 和 容斥原理 的推导。通过这个公式，我们可以高效地将差分数组 d[][] 的增量信息累加到原数组 a[][] 中，从而还原出每个位置的值。

四、 1.灵能传输 - 蓝桥云课

算法代码： 

#include <iostream>
#include <algorithm>
using namespace std;

#define ll long long
#define N 300005

ll sum[N], path[N];  // sum[] 存储前缀和，path[] 存储最终调整后的前缀和数组
bool mark[N];        // mark[] 用于标记某个前缀和是否已经被访问

int main()
{
    int n;
    cin >> n;  // 读取询问组数
    while(n--){
        int m;
        cin >> m;  // 读取每组询问的高阶圣堂武士数量
        fill_n(mark, N, false);  // 初始化 mark[] 数组为 false
        fill_n(sum, N, 0);       // 初始化 sum[] 数组为 0
        fill_n(path, N, 0);      // 初始化 path[] 数组为 0

        // 计算前缀和数组 sum[]
        for(int i = 1; i <= m; i++){
            cin >> sum[i];  // 读取灵能值
            sum[i] += sum[i - 1];  // 计算前缀和
        }

        ll begin = sum[0], end = sum[m];  // 记录前缀和数组的首尾项
        if(begin > end){
            swap(begin, end);  // 如果 begin > end，交换它们的值
        }

        sort(sum, sum + m + 1);  // 对前缀和数组进行排序

        // 找到排序后 begin 和 end 的下标
        for(int i = 0; i <= m; i++){
            if(sum[i] == begin){
                begin = i;  // 找到 begin 的下标
                break;
            }
        }
        for(int i = m; i >= 0; i--){
            if(sum[i] == end){
                end = i;  // 找到 end 的下标
                break;
            }
        }

        int left = 0, right = m;  // left 和 right 分别指向 path[] 的开头和末尾

        // 从 begin 开始，每隔一个元素赋值到 path[] 的开头
        for(int i = begin; i >= 0; i -= 2){
            path[left++] = sum[i];  // 赋值到 path[] 的开头
            mark[i] = true;         // 标记该前缀和已被访问
        }

        // 从 end 开始，每隔一个元素赋值到 path[] 的末尾
        for(int i = end; i <= m; i += 2){
            path[right--] = sum[i];  // 赋值到 path[] 的末尾
            mark[i] = true;         // 标记该前缀和已被访问
        }

        // 将未访问的前缀和按顺序赋值到 path[] 的中间
        for(int i = 0; i <= m; i++){
            if(!mark[i]){
                path[left++] = sum[i];  // 赋值到 path[] 的中间
            }
        }

        ll answer = 0;  // 初始化不稳定度为 0

        // 计算 path[] 中相邻元素的差值的最大值
        for(int i = 1; i <= m; i++){
            answer = max(answer, abs(path[i] - path[i - 1]));  // 更新不稳定度
        }

        cout << answer << endl;  // 输出每组询问的不稳定度
    }

    return 0;
}

         这段代码的主要目的是解决一个与 ​前缀和​ 和 ​不稳定度​ 相关的问题。以下是代码的详细思路和解释：

​代码思路

  1. ​问题描述：

    • 给定一个长度为 m 的数组，表示高阶圣堂武士的灵能值。
    • 通过调整数组的顺序，使得调整后的数组的前缀和数组的 ​不稳定度​ 最小。
    • 不稳定度定义为前缀和数组中相邻元素的差值的最大值。

  2. ​算法选择：

    • 使用 ​前缀和​ 和 ​排序​ 来构造满足条件的前缀和数组。
    • 通过 ​贪心策略​ 构造路径，使得相邻元素的差值尽可能小。

  3. ​代码结构：

    • 读取输入数据，计算前缀和数组。
    • 对前缀和数组进行排序。
    • 构造满足条件的前缀和数组 path[]。
    • 计算不稳定度并输出结果。

​代码详解

​1. 预处理

int n;
cin >> n;  // 读取询问组数
while(n--){
    int m;
    cin >> m;  // 读取每组询问的高阶圣堂武士数量
    fill_n(mark, N, false);  // 初始化 mark[] 数组为 false
    fill_n(sum, N, 0);       // 初始化 sum[] 数组为 0
    fill_n(path, N, 0);      // 初始化 path[] 数组为 0
  • 读取询问组数 n 和每组询问的数组长度 m。
  • 初始化 mark[]、sum[] 和 path[] 数组。

​2. 计算前缀和数组

for(int i = 1; i <= m; i++){
    cin >> sum[i];  // 读取灵能值
    sum[i] += sum[i - 1];  // 计算前缀和
}
  • 计算数组的前缀和 sum[]，其中 sum[i] 表示数组前 i 个元素的和。

​3. 记录首尾项并排序

ll begin = sum[0], end = sum[m];  // 记录前缀和数组的首尾项
if(begin > end){
    swap(begin, end);  // 如果 begin > end，交换它们的值
}

sort(sum, sum + m + 1);  // 对前缀和数组进行排序
  • 记录前缀和数组的首项 sum[0] 和尾项 sum[m]。
  • 如果 begin > end，交换它们的值。
  • 对前缀和数组 sum[] 进行排序。

​4. 找到首尾项的下标

for(int i = 0; i <= m; i++){
    if(sum[i] == begin){
        begin = i;  // 找到 begin 的下标
        break;
    }
}
for(int i = m; i >= 0; i--){
    if(sum[i] == end){
        end = i;  // 找到 end 的下标
        break;
    }
}
  • 在排序后的 sum[] 中找到 begin 和 end 的下标。

​5. 构造 path[] 数组

int left = 0, right = m;  // left 和 right 分别指向 path[] 的开头和末尾

// 从 begin 开始，每隔一个元素赋值到 path[] 的开头
for(int i = begin; i >= 0; i -= 2){
    path[left++] = sum[i];  // 赋值到 path[] 的开头
    mark[i] = true;         // 标记该前缀和已被访问
}

// 从 end 开始，每隔一个元素赋值到 path[] 的末尾
for(int i = end; i <= m; i += 2){
    path[right--] = sum[i];  // 赋值到 path[] 的末尾
    mark[i] = true;         // 标记该前缀和已被访问
}

// 将未访问的前缀和按顺序赋值到 path[] 的中间
for(int i = 0; i <= m; i++){
    if(!mark[i]){
        path[left++] = sum[i];  // 赋值到 path[] 的中间
    }
}
  • 使用 ​贪心策略​ 构造 path[] 数组：
    • 从 begin 开始，每隔一个元素赋值到 path[] 的开头。
    • 从 end 开始，每隔一个元素赋值到 path[] 的末尾。
    • 将未访问的前缀和按顺序赋值到 path[] 的中间。

​6. 计算不稳定度

ll answer = 0;  // 初始化不稳定度为 0

// 计算 path[] 中相邻元素的差值的最大值
for(int i = 1; i <= m; i++){
    answer = max(answer, abs(path[i] - path[i - 1]));  // 更新不稳定度
}

cout << answer << endl;  // 输出每组询问的不稳定度
  • 遍历 path[]，计算相邻元素的差值的最大值，即为不稳定度。
  • 输出结果。

​示例运行

假设输入如下：

n = 1
m = 5
灵能值 = [1, 2, 3, 4, 5]

运行代码后，输出为：

3

​总结

  • 这段代码通过 ​前缀和​ 和 ​排序​ 解决了不稳定度最小化的问题。
  • 使用 ​贪心策略​ 构造满足条件的前缀和数组，确保相邻元素的差值尽可能小。
  • 代码逻辑清晰，但需要注意数组下标和边界条件的处理。

http://www.kler.cn/a/586016.html

相关文章：

  • STM32---FreeRTOS消息队列
  • 16 | 实现简洁架构的 Store 层
  • Element Ui - 编辑时表单校验信息未清空问题处理
  • 作物移栽机器人的结构设计的介绍
  • Web后端开发之Maven
  • 2025年AI搜索引擎开源项目全景指南：从核心框架到生态工具
  • ARM64 架构地址空间分配深度解析
  • 79. 单词搜索:题解
  • sap关账+策略模式（避免大量if elseif）
  • SpringBoot注解驱动CRUD工具：spring-avue-plus
  • BOE(京东方)携手微博举办“微博影像年”年度影像大展 创新科技赋能专业影像惊艳呈现
  • 芯谷D8563TS：低功耗CMOS实时时钟/日历电路的优选方案
  • CentOS-7安装Docker（更新时间：2025-03-12）
  • markdown 转 word 工具 ‌Pandoc‌
  • 谷歌手机LEA流程
  • Vue 中的 transition 组件如何处理动画效果？
  • 世界坐标到UV纹理坐标的映射
  • PinnDE：基于物理信息神经网络的微分方程求解库
  • RabbitMQ入门：从安装到高级消息模式
  • axios配置全局接口超时时间