UVa 12788 Smooth Factor

题目描述

给定一个整数数组a1,a2,…,ana_1, a_2, \ldots, a_na1​,a2​,…,an​，定义其平滑因子为：最长的连续子数组ap,…,aqa_p, \ldots, a_qap​,…,aq​的长度，其中至多存在一个位置iii（p<i≤qp < i \leq qp<i≤q）满足ai−1>aia_{i-1} > a_iai−1​>ai​。换句话说，该子数组要么是完全非递减的，要么只包含一次“下降”。

要求对于多个测试用例，分别输出每个数组的平滑因子。

输入格式

• 多个测试用例，每个用例两行。
• 第一行：整数nnn（1≤n≤1051 \leq n \leq 10^51≤n≤105）。
• 第二行：nnn个整数a1,…,ana_1, \ldots, a_na1​,…,an​（0≤∣ai∣<1080 \leq |a_i| < 10^80≤∣ai​∣<108）。

输出格式

• 每个测试用例一行，输出对应数组的平滑因子。

样例输入

3 1 2 3 1 0 8 1 2 1 2 1 2 3 1 4 1 -10 -100 -100

样例输出

3 1 5 3

题目分析

本题要求寻找满足“至多包含一次下降”的最长连续子数组的长度。这里的“下降”指的是ai−1>aia_{i-1} > a_iai−1​>ai​。换句话说，在子数组中，最多只能有一个位置使得前一个元素大于后一个元素。

关键点

1. 连续性：子数组必须是原数组的连续一段。
2. 至多一次下降：允许000次或111次下降。
3. 高效计算：nnn最大可达10510^5105，需要O(n)O(n)O(n)或O(nlog⁡n)O(n \log n)O(nlogn)的算法。

思路推导

我们可以将问题转化为一个滑动窗口问题：

• 维护一个窗口[left,right][left, right][left,right]。
• 用计数器dropCountdropCountdropCount记录窗口内下降的次数。
• 当dropCount≤1dropCount \leq 1dropCount≤1时，窗口有效，可以扩展右边界。
• 当dropCount>1dropCount > 1dropCount>1时，窗口无效，需要移动左边界直到dropCount≤1dropCount \leq 1dropCount≤1。
• 在移动左边界时，如果移出的位置原本是一个下降点，则dropCountdropCountdropCount需要减111。
• 每次窗口有效时，用当前窗口长度更新答案。

这样，我们通过一次遍历就能找到最长满足条件的子数组。

算法步骤

1. 初始化left=0left = 0left=0，maxLen=1maxLen = 1maxLen=1（至少长度为111），dropCount=0dropCount = 0dropCount=0。
2. 遍历右边界rightrightright从111到n−1n-1n−1：
   • 判断a[right−1]>a[right]a[right-1] > a[right]a[right−1]>a[right]？如果是，则dropCountdropCountdropCount加111。
   • 当dropCount>1dropCount > 1dropCount>1时：
     • 若a[left]>a[left+1]a[left] > a[left+1]a[left]>a[left+1]，则dropCountdropCountdropCount减111。
     • leftleftleft加111。
   • 计算当前窗口长度right−left+1right - left + 1right−left+1，更新maxLenmaxLenmaxLen。
3. 输出maxLenmaxLenmaxLen。

时间复杂度：O(n)O(n)O(n)，每个元素至多被访问两次。
空间复杂度：O(1)O(1)O(1)（不计输入数组）。

代码实现

// Smooth Factor// UVa ID: 12788// Verdict: Accepted// Submission Date: 2025-12-15// UVa Run Time: 0.010s//// 版权所有（C）2025，邱秋。metaphysis # yeah dot net#include<bits/stdc++.h>usingnamespacestd;intmain(){ios::sync_with_stdio(false);cin.tie(nullptr);intn;while(cin>>n){vector<int>a(n);for(inti=0;i<n;++i)cin>>a[i];intleft=0,maxLen=1;// 至少长度为1intdropCount=0;// 窗口中下降的次数for(intright=1;right<n;++right){// 判断 right 是否为下降点if(a[right-1]>a[right])dropCount++;// 如果下降次数超过1，移动左边界直到满足条件while(dropCount>1){// 如果 left 是下降点，移出窗口时减少计数if(a[left]>a[left+1])dropCount--;left++;}// 更新最大长度maxLen=max(maxLen,right-left+1);}cout<<maxLen<<"\n";}return0;}

示例分析

以样例1 2 1 2 1 2 3 1为例：

• 最长满足条件的子数组为1 2 1 2 3，长度为555。
• 其中只有一次下降（2>12 > 12>1），其余位置均非递减。

算法过程：

• 窗口滑动过程中，当遇到第二次下降时（例如3>13 > 13>1），左边界移动，直到窗口中只保留一次下降，从而找到最长窗口。

总结

本题通过滑动窗口维护一个至多包含一次下降的连续子数组，在O(n)O(n)O(n)时间内求解。关键在于用dropCountdropCountdropCount记录下降次数，并通过移动左边界保持条件成立。代码简洁高效，适用于大数据范围。