嘉兴建站模板系统,怀化网站开发,一个网站开发周期,微网站制作提供商推荐CSP-202109-2-非零段划分
关键点#xff1a;差分数组
详见#xff1a;【CSP考点回顾】差分数组
时间复杂度分析 使用差分数组的优势在于#xff0c;它将问题转化为了在一次遍历中识别并利用关键变化点#xff08;波峰和波谷#xff09;#xff0c;从而避免了对每个可能…CSP-202109-2-非零段划分
关键点差分数组
详见【CSP考点回顾】差分数组
时间复杂度分析 使用差分数组的优势在于它将问题转化为了在一次遍历中识别并利用关键变化点波峰和波谷从而避免了对每个可能子数组的重复检查。这种方法利用了问题的特殊结构——即只有在特定的转折点才需要更新我们的计数——来大幅度减少必要的计算量。因此在处理大数据量时差分数组方法的效率远高于暴力枚举法。 暴力枚举法70分 在暴力枚举方法中尝试每个可能的子数组然后检查每个子数组是否符合条件是否是非零段。对于每个长度为 n 的数组有 n ( n 1 ) / 2 n(n1)/2 n(n1)/2 种可能的子数组因为我们可以从数组的每个位置开始选择不同的结束位置。对于每个子数组我们需要 O ( m ) O(m) O(m) 的时间来验证它是否是一个非零段其中 m 是子数组的长度。因此总的时间复杂度将会是 O ( n 3 ) O(n^3) O(n3)因为对于每个子数组我们都进行了线性时间的检查。 差分数组法100分 使用差分数组的方法我们首先通过一次遍历 O ( n ) O(n) O(n) 时间复杂度处理原数组来建立差分数组并进行初始化处理例如标记波峰和波谷。接下来我们再次遍历差分数组又是 O ( n ) O(n) O(n) 时间复杂度来计算最长的非零段。在这次遍历中我们累积差分值并记录最大的累积值。因此整个过程的时间复杂度是 O ( n ) O ( n ) O ( n ) O(n) O(n) O(n) O(n)O(n)O(n)远低于暴力枚举方法的 O ( n 3 ) O(n^3) O(n3)。
解题思路
使用向量 A在其开始和结束位置添加额外的零元素以符合问题中提到的非零段定义。使用 unique 函数对数组 A 进行去重即连续重复的元素只保留一个因为连续的相同值不会影响非零段的长度。通过遍历数组 A计算差分数组 diff在波峰位置加一在波谷位置减一。这里波峰指的是 A[i] 比它前后的元素都要大的情况波谷指的是 A[i] 比它前后的元素都要小的情况详见下图。 在这个问题中使用“波峰”和“波谷”的概念来加一或减一实际上是利用差分数组的特性来标记数组中的重要转变点。我们利用差分数组来记录特定模式的出现——即数组中的极值点。 为什么在波峰位置加一 波峰定义为一个元素其值大于其前后的元素A[i-1] A[i] A[i1]。在这个位置加一是为了标记一个上升段的结束和下降段的开始。这是非零段可能的开始或结束因为在实际应用中一个上升然后下降的序列波峰意味着我们找到了一个完整的子段这可能是我们寻找的非零段的一部分。 为什么在波谷位置减一 波谷定义为一个元素其值小于其前后的元素A[i-1] A[i] A[i1]。在这个位置减一是为了标记一个下降段的结束和上升段的开始。这也是非零段可能的开始或结束因为它标志着一个低谷即从高值下降到低值的转变点。 遍历差分数组 diff累加当前值到 sum并更新 noneZeroMax用来记录遇到的最大的非零段长度。sum 的计算方式保证了我们只在非零段内进行计数并且每次遇到非零段时都检查是否能更新最大长度。
完整代码
#include iostream
#include vector
#include algorithm
using namespace std;int n, sum, noneZeroMax;
vectorintdiff(50000); // 差分数组int main() {cin n;vectorintA(n 2, 0); // A的第一个和最后一个元素置零非零段定义for (int i 1; i n; i){cin A[i];}auto last unique(A.begin(), A.end()); // 去重A.erase(last, A.end());// 计算差分数组波峰1波谷-1for (int i 1; i A.size() - 2; i){if (A[i - 1] A[i] A[i] A[i 1]) diff[A[i]];if (A[i - 1] A[i] A[i] A[i 1]) diff[A[i]]--;}// 统计最大非零段for (int i diff.size()-1; i 0; i--){sum diff[i];noneZeroMax max(sum, noneZeroMax);}cout noneZeroMax;return 0;
}
