题目描述
给定 n,k 和一个长度为 n 的序列, 求最长的最大值最小值相差不超过 k 的序列
输入格式
第一行两个有空格隔开的整数 k(0<=k<=2000,000,000),n(1<=n<=3000,000),k 代表设定的最大值, n 代表序列的长度. 第二行为 n 个由空格隔开的整数 ai(1<=ai<=2000,000,000), 表示序列.
输出格式
一个整数代表最大的符合条件的序列
首先解释一下题目: 这道题让我们求出一个长度为 n 的序列中最长的一段子序列, 满足这段子序列的最大值减最小值的差不超过 k, 求子序列的最大长度.
因为单调队列可以记录下一段区间的最大值和最小值, 所以这道题我们完全可以用一个单调队列来实现.
我们设立一个 l 和 r 变量, 分别表示子区间的左边界和右边界. 接下来我们对任意一个子序列进行移动:
移动操作有两种情况, 第一种即当该单调区间的最大值减去最小值的差小于等于 k 时, 该单调区间是一个合法的区间. 这时我们可以对答案进行记录, 然后让 r++, 再进行判断是否会有更大的区间.
第二种情况, 即当该单调区间的最大值减去最小值的差大于 k 时, 该区间是一个不合法的区间. 这时候我们不能将 r++, 因为这种操作不可能减小该区间内的最大值或增大该区间内的最小值, 使变成一个合法的区间. 我们只能将 l++, 然后注意要根据之前的 a[l] 和 maxn,minn 之间关系的三种情况对最大值和最小值进行维护. 注意, 单调队列是单调的, 它只能往右移动, 绝对不能出现往左移动的状况, 即绝对不能 l-- 或 r--
这样我们就成功维护了单调队列的操作.
代码:
- #include<bits/stdc++.h>
- using namespace std;
- const int inf=0x3f3f3f3f;
- int k,n,l,r,maxn,minn,ans;
- int a[3000005];
- void find(int l,int r){
- maxn=-inf;minn=inf;
- for(int i=l;i<=r;i++){
- maxn=max(maxn,a[i]);
- minn=min(minn,a[i]);
- }
- }
- int main(){
- cin>>k>>n;
- for(int i=1;i<=n;i++){
- cin>>a[i];
- }
- l=1;r=2;
- maxn=max(a[1],a[2]);
- minn=min(a[1],a[2]);
- while(1){
- if(maxn-minn>k){
- if((a[l]==minn)||(a[l]==maxn)){
- l++;
- find(l,r);
- }else if(a[l]>minn){
- l++;
- }
- }else{
- r++;
- if(a[r]<minn){
- minn=a[r];
- }else if(a[r]>maxn){
- maxn=a[r];
- }
- if(maxn-minn<=k){
- ans=max(ans,r-l+1);
- }
- }
- if(r==n){
- break;
- }
- }
- cout<<ans<<endl;
- return 0;
- }
来源: http://www.bubuko.com/infodetail-3683645.html