CSP-202109-2-非零段劃分
【70分思路-暴力枚舉】
這段代碼的目的是在給定一個由自然數（非負整數）組成的數組后，通過選擇一個適當的正整數 p，將數組中所有小于 p 的數變為 0，從而使得數組中非零段的數量達到最大。這里的非零段是指連續的、非零的數組元素序列。
程序的主要邏輯分為以下幾個步驟：
-
讀取數組長度 n 和數組元素，同時找出數組中的最大元素 maxElem。
-
對于每一個可能的 p 值（從 1 到 maxElem），復制原始數組并將所有小于 p 的元素設置為 0。
-
對于每個 p 值的新數組，遍歷數組來計算非零段的數量。一個非零段開始于一個非零元素，該元素要么是數組的第一個元素，要么其前一個元素為零。非零段結束于數組的最后一個元素或一個非零元素后跟著一個零元素。
-
更新并記錄非零段數量的最大值。
-
輸出非零段的最大數量。
時間復雜度
-
第一層循環（讀取數組）的時間復雜度為 O(n)，n 是數組的長度。
-
第二層循環是對于每一個可能的 p 值進行迭代，其最壞情況下的時間復雜度為 O(maxElem)。
-
在每一個 p 的值下，我們又對數組進行了兩次遍歷（一次是將小于 p 的值置為 0，另一次是計算非零段的數量），每次遍歷的時間復雜度為 O(n)。
因此，整個程序的總時間復雜度為 O(maxElem * n)，這里 maxElem 是數組中的最大值，n 是數組的長度。由于 maxElem 可能接近 n，所以在最壞情況下，時間復雜度可以近似為 O(n^2)。
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
vector<int>arr;int main() {long long n;int maxNum = -1, maxElem = -1;cin >> n;for (int i = 0; i < n; i++){int t;cin >> t;arr.push_back(t);maxElem = max(maxElem, t);}for (int p = 1; p <= maxElem; p++){// 小于 p 的數都變為 0for (auto& it : arr) {if (it < p) it = 0;}int num = 0;bool flag = 1; // 1-上一位是0；0-上一位不是零// 統計非零段for (auto& it : arr) {if (it != 0) {if (flag) {num++;}flag = 0;}else{flag = 1;}}// 記錄最大非零段數maxNum = max(maxNum, num);}cout << maxNum;return 0;
}
【100分思路-差分數組】
-
初始化和輸入處理：定義了兩個向量
numbers和diff，分別用于存儲輸入的數列和差分數組。numbers的大小比實際數列長度多2，這是為了在數列的開始和結束添加邊界值0，以方便處理。 -
去重和邊界處理：使用
unique函數去除連續的重復元素，這對于減少不必要的計算特別有效，因為連續的相同數值不會增加非零段的數量。 -
差分數組的構建:
- 差分數組
diff用于記錄每個可能的數值對應的變化（峰值增加，谷值減少）。這實際上是對數列進行一種“轉化”，使得后續的求解更加直接和高效。 - 遍歷數列，如果當前數字是一個峰值（即比前一個和后一個數都大），則在差分數組對應位置加一；如果是谷值（即比前一個和后一個數都小），則減一。
- 差分數組
-
通過差分數組求解答案:
- 通過遍歷差分數組的累加和（即從后向前計算前綴和），可以找出使非零段數量最大化的數值。這是因為差分數組的前綴和反映了在當前閾值下，非零段的增減情況。
時間復雜度
- 初始化和輸入處理：O(N)，其中N是數列的長度。
- 去除連續重復元素：最壞情況下O(N)，因為需要檢查每個元素是否與前一個相同。
- 構建差分數組：O(N)，每個元素至多被訪問一次。
- 通過差分數組求解答案：O(V)，其中V是數值的最大可能值，這里是
MAX_VALUE。 - 因此，總體時間復雜度為O(N + V)，其中N是數列的長度，V是數值的最大可能范圍。
#include <iostream>
#include <vector>
#include <algorithm>
#include <cstring>
using namespace std;const int MAX_NUM = 500000; // 最大數字數量
const int MAX_VALUE = 10000; // 最大值
vector<int> numbers(MAX_NUM + 2); // 使用vector存儲輸入的數列
vector<int> diff(MAX_VALUE + 1); // 使用vector存儲差分數組int main() {int length;cin >> length;for (int i = 1; i <= length; i++) {cin >> numbers[i];}numbers[0] = numbers[length + 1] = 0; // 將邊界設置為0// unique函數去除連續重復元素，更新vector的有效長度length = unique(numbers.begin(), numbers.begin() + length + 2) - numbers.begin() - 1;// 初始化差分數組為0fill(diff.begin(), diff.end(), 0);for (int i = 1; i < length; i++){if (numbers[i - 1] < numbers[i] && numbers[i] > numbers[i + 1]) {diff[numbers[i]]++; // 如果是峰值，對應的差分數組加一}else if (numbers[i - 1] > numbers[i] && numbers[i] < numbers[i + 1]) {diff[numbers[i]]--; // 如果是谷值，對應的差分數組減一}}// 通過差分數組求解答案int maxSegments = 0, sum = 0; // maxSegments記錄最終答案，sum記錄差分的前綴和for (int i = MAX_VALUE; i >= 1; i--) {sum += diff[i]; // 累加差分得到前綴和maxSegments = max(maxSegments, sum); // 更新答案}cout << maxSegments << endl; return 0;
}
學習)
