首页 > 代码库 > 6E-差值不超过k的子段个数
6E-差值不超过k的子段个数
给n个数,然后找出最长的一段子序列(不需要连续),使得这段子序列中的最大值与最小值之间的差值不超过k.找出有几个子序列满足,并输出他们的开始位置和结束位置
#include <cstdio>#include <iostream>using namespace std;int n,k,a[100005];int Max[100005],Min[100005],h1,t1,h2,t2,j;inline int Get_Max(){ return a[Max[h1+1]];}inline int Get_Min(){ return a[Min[h2+1]];}inline void Update(){ while (Max[h1+1]<j) h1++; while (Min[h2+1]<j) h2++;}inline void Push(int x){ while (h1!=t1 && a[x]>=a[Max[t1]]) t1--; Max[++t1]=x; while (h2!=t2 && a[x]<=a[Min[t2]]) t2--; Min[++t2]=x;}int ans=1;int _O_[100005],_cnt=0;int main(){ scanf("%d%d",&n,&k); for (int i=1;i<=n;i++) scanf("%d",a+i); Push(1); _O_[_cnt=1]=1; Max[t1=1]=Min[t2=1]=1; j=1; for (int i=2;i<=n;i++) { Push(i); while (Get_Max()-Get_Min()>k) j++,Update(); if (i-j+1>ans) { ans=i-j+1; _O_[_cnt=1]=j; } else if (i-j+1==ans) { _O_[++_cnt]=j; } } printf("%d %d\n",ans,_cnt); for (int i=1;i<=_cnt;i++) printf("%d %d\n",_O_[i],_O_[i]+ans-1); return 0;}
6E-差值不超过k的子段个数
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。