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

devtools/2025/3/15 14:53:38/

一、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];// 计算未排序时的累加结果 ans1for (int i = 1; i <= n; i++) ans1 += (long long)a[i] * cnt[i];// 排序 a[] 和 cnt[]，计算排序后的累加结果 ans2sort(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 行开始，空白区域的数量增加 1d[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 300005ll 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[] 数组为 falsefill_n(sum, N, 0);       // 初始化 sum[] 数组为 0fill_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[] 数组为 falsefill_n(sum, N, 0);       // 初始化 sum[] 数组为 0fill_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.ppmy.cn/devtools/167312.html

相关文章

泛目录程序：无需数据库的高效站群解决方案

泛目录程序：无需数据库的高效站群解决方案

泛目录程序&#xff1a;无需数据库的高效站群解决方案 在当今快速发展的互联网环境中&#xff0c;网站运营者面临着越来越多的挑战&#xff0c;包括如何提高网站的运行效率、降低资源消耗以及保障数据安全。针对这些需求&#xff0c;2025奥顺互联推出了一款无需数据库支持的泛…
阅读更多...
使用热门AI工具LLMPerf和LiteLLM对Amazon Bedrock上私有化部署的的DeepSeek-R1进行基准测试

使用热门AI工具LLMPerf和LiteLLM对Amazon Bedrock上私有化部署的的DeepSeek-R1进行基准测试

开源的基础模型使AI行业的开发者与企业能够通过微调来开发拥有特定领域知识&#xff0c;并且满足特定需求的定制化AI应用&#xff0c;同时保持低成本和对模型和数据管理的控制。然而开源模型的弊端则是部署往往占据整个项目超30%的时间&#xff0c;因为工程师需要通过反复测试来…
阅读更多...
【人工智能】Transformer、BERT、GPT：区别与联系

【人工智能】Transformer、BERT、GPT：区别与联系

Transformer、BERT、GPT：区别与联系 近年来，Transformer、BERT、GPT 等模型在自然语言处理领域取得了巨大成功，深刻改变了我们对语言理解和生成的认识。它们之间既有区别，又存在紧密联系，共同推动了 NLP 的发展。 一、Transformer：革命性的架构 Transformer 是这一切的…
阅读更多...
PN结和三极管

PN结和三极管

知其然&#xff0c;更要知其所以然 文章目录 1. 从PN结说起1.1 P型半导体1.2 N型半导体1.3 PN结的形成1.4 PN结的特性1.4.1 单向导电性1.4.2 伏安特性 2. 三极管2.1 NPN型三极管2.2 PNP型三极管 1. 从PN结说起 三极管由两个PN结构成&#xff0c;所以想要认识三极管&#xff0c…
阅读更多...
使用PHP进行自动化测试：工具与策略的全面分析

使用PHP进行自动化测试：工具与策略的全面分析

使用PHP进行自动化测试&#xff1a;工具与策略的全面分析 引言 随着软件开发的复杂性不断增加&#xff0c;自动化测试已成为确保软件质量的关键环节。PHP作为一种广泛使用的服务器端脚本语言&#xff0c;拥有丰富的生态系统和工具支持&#xff0c;使其成为自动化测试的理想选…
阅读更多...
SSL 原理及实验

SSL 原理及实验

引言 为了实现远程办公或者远程客户访问内网的资源 &#xff08;1&#xff09;回顾历史&#xff1a; 起初先出现SSL(Secure Sockets Layer&#xff09;&#xff0d;安全套接层协议。 美国网景Netscape公司1994年研发&#xff0c;介于传输层TCP协议和应用层协议之间的一种协议…
阅读更多...
深度学习和机器学习的差异

深度学习和机器学习的差异

一、技术架构的本质差异 传统机器学习&#xff08;Machine Learning&#xff09;建立在统计学和数学优化基础之上&#xff0c;其核心技术是通过人工设计的特征工程&#xff08;Feature Engineering&#xff09;构建模型。以支持向量机&#xff08;SVM&#xff09;为例&#xf…
阅读更多...
语言识别模型whisper学习笔记

语言识别模型whisper学习笔记

语言识别模型whisper学习笔记 Whisper 是由 OpenAI 于 2022年9月 推出的开源自动语音识别&#xff08;ASR&#xff09;系统&#xff0c;旨在实现高精度、多语言的语音转文本及翻译任务。其核心目标是解决传统语音识别模型在噪声环境、口音多样性及多语言场景下的局限性。 一、…
阅读更多...
最新文章

Copyright @ 2022~2023