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。换句话说，在子数组中，最多只能有一个位置使得前一个元素大于后一个元素。

关键点

连续性：子数组必须是原数组的连续一段。
至多一次下降：允许000次或111次下降。
高效计算：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。
每次窗口有效时，用当前窗口长度更新答案。

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

算法步骤

初始化left=0left = 0left=0，maxLen=1maxLen = 1maxLen=1（至少长度为111），dropCount=0dropCount = 0dropCount=0。
遍历右边界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。
输出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;}