最长连续子序列
题目 最长连续子序列
思路分析
题意转换为找出一段数 它们的平均值大于100
关于平均数的技巧 之前 最佳牛围栏 里有遇到过
尝试把每个数都减去平均数
这样就可以从 判断一个分式是否大于某数 转换为 判断一段加法是否大于0的问题
对一段数进行操作 显然是前缀和问题
将他们再转变成s[r]-s[l-1]的问题
那么再分析一下 就可以变成找s[r]左边的一个小于它的数
可以联想到单调栈
但是单调栈找的是最近的一个 并不符合我们要找最长（最左边的那个小于s[r]的数）
也就是说 这里不能随便出栈了 当前数右边的数可能拿它左边的数当答案 而不是确保当前数（栈顶）就是最佳答案 不过相同之处就是 如果出现违背递减的趋势 它还是要被舍弃的（如果这个较大的数能作为答案 那么它左边的数一定能作为更合适的答案 为什么 ？1、更靠左 2、大的都比s[r]小 小的更别说了） 所以 我们要的数还是单调递减的 所以可以沿用单调栈的思想 只不过对出栈逻辑做了一些变动（所以单减的都入栈）
现在问题变成了这样 栈顶是最近的一个小于s[r]的数 但不一定是最左边的
而那个答案一定在我们的单调栈中
那么 就可以用二分在单调栈中找到那个最左的小于s[r]的数的下标
（为什么要先单调栈再二分 而不直接二分——原序列并不具有二段性和单调性 单调栈构造出了一个单减的答案区间 构造出了二段性 这样才能用二分）
这里的二分也有所变动
因为之前做的都是单增的二分 现在变成了单减 mid逻辑有些相反
来分析一下
找的是小于的数 不包含等于
所以区间划分成≥,<
答案取的是右区间的最左的数
若取一个mid 使得小了 说明答案应该在左边 所以r=mid
这样一来 check条件 和模板就都确定了
代码实现
#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
const int N=1e6+10;
LL s[N];//小技巧：如果最后一个数据没过 很有可能是爆int了
int stk[N];
int n;
int main()
{
cin>>n;
for(int i=1;i<=n;i++){
int x;cin>>x;
s[i]=s[i-1]+x-100;
}
int top=0;
int res=0;
stk[++top]=0;
for(int i=1;i<=n;i++){
if(s[i]<s[stk[top]])
stk[++top]=i;
else if(s[i]>s[stk[top]]){
int l=1,r=top;
while(l<r){
int mid=l+r>>1;
if(s[stk[mid]]<s[i])
r=mid;
else
l=mid+1;
}
res=max(res,i-stk[r]);
}
}
cout<<res<<endl;
return 0;
}
💬 评论