差分專題練習 ——基于羅勇軍老師的《藍橋杯算法入門C/C++》

一、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.pswp.cn/bicheng/73342.shtml
繁體地址，請注明出處：http://hk.pswp.cn/bicheng/73342.shtml
英文地址，請注明出處：http://en.pswp.cn/bicheng/73342.shtml

如若內容造成侵權/違法違規/事實不符，請聯系多彩編程網進行投訴反饋email:809451989@qq.com，一經查實，立即刪除！

相關文章

AI+視頻監控電力巡檢：EasyCVR視頻中臺方案如何賦能電力行業智能化轉型

AI+視頻監控電力巡檢：EasyCVR視頻中臺方案如何賦能電力行業智能化轉型

隨著電力行業的快速發展&#xff0c;電力設施的安全性、穩定性和運維效率變得至關重要。傳統視頻監控系統在實時性、智能化及多系統協同等方面面臨嚴峻挑戰。EasyCVR視頻中臺解決方案作為一種先進的技術手段&#xff0c;在電力行業中得到了廣泛應用&#xff0c;為電力設施的監控…
閱讀更多...
【哈希表與字符串的算法之路：思路與實現】—— LeetCode

【哈希表與字符串的算法之路：思路與實現】—— LeetCode

文章目錄 兩數之和面試題01.02.判定是否為字符重排存在重復元素存在重復元素||字母異位詞分組最長公共前綴和最長回文子串二進制求和字符串相乘 兩數之和 這題的思路很簡單&#xff0c;在讀完題目之后&#xff0c;便可以想到暴力枚舉&#xff0c;直接遍歷整個數組兩遍即可&…
閱讀更多...
RabbitMQ入門：從安裝到高級消息模式

RabbitMQ入門：從安裝到高級消息模式

文章目錄 一. RabbitMQ概述1.1 同步/異步1.1.1 同步調用1.1.2 異步調用 1.2 消息中間件1.2.1 概念1.2.2 作用1.2.3 常見的消息中間件1.2.4 其他中間件 1.3 RabbitMQ1.3.1 簡介1.3.2 特點1.3.3 方式1.3.4 架構1.3.5 運行流程 二. 安裝2.1 Docker 安裝 RabbitMQ 三. 簡單隊列&…
閱讀更多...
kernel與modules解耦

kernel與modules解耦

一、耦合&#xff1a; linux的kernel與modules存在耦合版本匹配&#xff0c;在版本不匹配&#xff08;內核重新編譯后&#xff0c;或者驅動模塊編譯依賴的內核版本跟運行版本不匹配&#xff09;時候&#xff0c;會存在insmod 驅動模塊失敗的情形&#xff1b; 二、解耦&#xff…
閱讀更多...
物理約束神經網絡（PINN）和有限元方法哪個更接近“真正的物理規律”？還是兩者只是不同的數學表達？

物理約束神經網絡（PINN）和有限元方法哪個更接近“真正的物理規律”？還是兩者只是不同的數學表達？

物理約束神經網絡（Physics-Informed Neural Networks, PINN）和有限元方法（Finite Element Method, FEM）是兩種在科學計算和工程模擬中廣泛應用的數值方法。PINN 依賴深度學習來近似微分方程的解，并在訓練過程中將物理約束作為損失項融入網絡，而 FEM 通過將連續介質的物理…
閱讀更多...
UI程序的std::cout重定向輸出到Visual Studio的debug輸出窗口

UI程序的std::cout重定向輸出到Visual Studio的debug輸出窗口

常用代碼。 UI程序的std::cout重定向輸出到Visual Studio的debug輸出窗口 #include <iostream> #include <streambuf> #include <vector> #include <string> #include <afxwin.h> //MFC// 自定義 streambuf 類&#xff0c;用于重定向輸出到 Vis…
閱讀更多...
Python開發合并多個PDF文件

Python開發合并多個PDF文件

前言 在我們的工作中&#xff0c;可能有以下場景需要用到合并多個PDF&#xff1a; 文檔歸檔&#xff1a;在企業或組織中&#xff0c;常常需要將相關的文檔&#xff08;如合同、報告、發票等&#xff09;合并為一個PDF文件&#xff0c;以便于歸檔和管理。 報告生成&#xff1a;在…
閱讀更多...
DeepSeek 助力 C++ 開發：探索智能編程新境界

DeepSeek 助力 C++ 開發：探索智能編程新境界

這篇文章就會詳細講講 DeepSeek 在 C 開發里到底能怎么用&#xff0c;從上面說的寫代碼、找錯誤、優化性能&#xff0c;到管理項目這些方面&#xff0c;還會給出好多實際的代碼例子&#xff0c;講講實際用起來是啥情況。目的就是給那些做 C 開發的人&#xff0c;一份全面又詳細…
閱讀更多...
C#-使用VisualStudio編譯C#工程

C#-使用VisualStudio編譯C#工程

一.創建csproj文件 二.創建源cs文件 三.生成解決方案 四.運行解決方案 五.VisualStudio功能列表 <1.代碼格式化: CtrlKD完成代碼整體格式化 <2.窗口布局 窗口->重置窗口布局 <3.引用查找&關聯 <4.包管理 <5.日志輸出級別 工具->選項->項目解決方案…
閱讀更多...
Kafka相關的面試題

Kafka相關的面試題

以下是150道Kafka相關的面試題及簡潔回答&#xff1a; Kafka基礎概念 1. 什么是Kafka&#xff1f; Kafka是一個分布式、可擴展、容錯的發布-訂閱消息系統&#xff0c;最初由LinkedIn開發&#xff0c;現為Apache項目。它適用于高吞吐量的場景&#xff0c;如大數據處理和實時數據…
閱讀更多...
CTF--Web安全--SQL注入之報錯注入

CTF--Web安全--SQL注入之報錯注入

CTF–Web安全–SQL注入之報錯注入 一、報錯注入的概念 用戶使用數據庫查詢語句&#xff0c;向數據庫發送錯誤指令&#xff0c;數據庫返回報錯信息&#xff0c;報錯信息中參雜著我們想要獲取的隱私數據。通常在我們在頁面顯示中找不到回顯位的時候&#xff0c;使用報錯注入。 二…
閱讀更多...
深度學習中學習率調整策略

深度學習中學習率調整策略

學習率衰減策略是深度學習優化過程中的一個關鍵因素&#xff0c;它決定了訓練過程中學習率的調整方式&#xff0c;從而影響模型收斂的速度和效果。不同的衰減策略在不同的任務和模型上可能有不同的表現&#xff0c;下面從我用到過的幾個衰減策略進行記錄&#xff0c;后續慢慢跟…
閱讀更多...
JavaCV

JavaCV

調用攝像頭 public class Camera {public static void main(String[] args) throws FrameGrabber.Exception {// 開啟抓取器OpenCVFrameGrabber grabber new OpenCVFrameGrabber(0);grabber.start();// 開啟窗口CanvasFrame canvasFrame new CanvasFrame("OpenCV Frame…
閱讀更多...
凝思linux修改mac地址

凝思linux修改mac地址

臨時性修改 /sbin/ifconfig eth0 hw ether 00:0C:29:36:97:20
閱讀更多...
前端UI編程基礎知識：基礎三要素（結構→表現→行為）

前端UI編程基礎知識：基礎三要素（結構→表現→行為）

以下是重新梳理的前端UI編程基礎知識體系&#xff0c;結合最新技術趨勢與實戰要點&#xff0c;以更適合快速掌握的邏輯結構呈現&#xff1a; 一、基礎三要素&#xff08;結構→表現→行為&#xff09; 1. HTML5 核心能力 ? 語義化標簽&#xff1a;<header>, <nav&g…
閱讀更多...
面試題：實現學生管理系統

面試題：實現學生管理系統

這是我在以前面試中遇到的一個問題&#xff0c; 面試官說&#xff1a;你能現場實現一個學生管理系統嗎&#xff0c;實現對學生的增刪查改這4個功能 當時寫了半天沒寫出來.....&#xff0c;所以我在這里記錄一下 10分鐘實現學生管理系統并實現 增刪查改 功能 #include <iostr…
閱讀更多...
大語言模型基礎—語言模型的發展歷程--task1

大語言模型基礎—語言模型的發展歷程--task1

目錄 1.語言模型的發展歷程 1.1 統計語言模型 1.2 神經語言模型 1.3 預訓練語言模型 1.4 大語言模型 1.5 總結 1.6 各階段對比與演進邏輯 1.語言模型的發展歷程 語言模型的發展歷程經歷了四個主要階段&#xff1a;統計語言模型、神經語言模型、預訓練語言模型和大語言模…
閱讀更多...
BIG_EVENT

BIG_EVENT

環境準備: 開發: 跨域問題: 只有瀏覽器才存在跨域問題, 此時瀏覽器的地址和前端服務一致,所以不存在跨域問題, 但是當瀏覽器中的js代碼需要向8080發送請求時就會由于存在跨域問題而失敗. 簡單的說前端和瀏覽器的地址端口是一致的,瀏覽器只能向前端服務發送請求, 所以可以使用配…
閱讀更多...
DAY33 貪心算法Ⅱ

DAY33 貪心算法Ⅱ

122. 買賣股票的最佳時機 II - 力扣&#xff08;LeetCode&#xff09; 想到把整體利潤分解為每天的利潤&#xff0c;就豁然開朗了。 class Solution { public:int maxProfit(vector<int>& prices) {int result0;for(int i1;i<prices.size();i){resultmax(0,pric…
閱讀更多...
【Qt】qApp簡單介紹

【Qt】qApp簡單介紹

1. 介紹 在Qt中&#xff0c;qApp是一個全局指針&#xff0c;它指向當前的QApplication或QGuiApplication對象。這個全局指針在Qt應用程序中非常有用&#xff0c;因為它可以讓你在任何地方訪問到應用程序對象。 在C中&#xff0c;全局指針是一個可以在程序的任何地方訪問的指針…
閱讀更多...
最新文章

Copyright @ 2022~2023