[POI2010]PIL-Pilots

摘要

近期以 POI 的题为主,因为小清新~

题意:给定 n,k 和一个长度为 n 的序列,求最长的最大值最小值相差不超过 k 的子串

最大最小就是单调队列啦,又因为是找连续子串的最大长度,显然就是尺取法的思路,每次纳入一个新的元素时更新两个队列,然后判断相差是否大于 k,如果大了就删去队首元素(两个队列的队首优先删掉下标靠前的元素),然后更新答案即可.

鉴于内存较小,因此队列中可以只记录下标

#include<bits/stdc++.h>
using namespace std;
const int N=3e6+6;
int n,k;
int a[N];
int q1[N],l1,r1;
int q2[N],l2,r2;
int main(){scanf("%d%d",&k,&n);
    for(int i=1;i<=n;i++)scanf("%d",&a[i]);
    l1=l2=1,r1=r2=0;
    q1[++r1]=1,q2[++r2]=1;// 队列记录下标
    int ans=1,cur=1;
    for(int i=2;i<=n;i++){while(l1<=r1&&a[q1[r1]]<a[i])r1--; 
        q1[++r1]=i;
        while(l2<=r2&&a[q2[r2]]>a[i])r2--; 
        q2[++r2]=i;
        while(a[q1[l1]]-a[q2[l2]]>k){if(q1[l1]<q2[l2])cur=q1[l1]+1,++l1;
            else cur=q2[l2]+1,++l2;
        }
        ans=max(ans,i-cur+1);
    }
    printf("%d",ans);
    return 0;
}

  转载请注明: Sshwy's Blog [POI2010]PIL-Pilots

 上一篇
[POI2013]BAJ-Bytecomputer [POI2013]BAJ-Bytecomputer
摘要 题意:一个序列只有 ,每次可以选一个 使 ,求操作最少次数使得整个序列非严格单调递增. 小清新的 DP 题~ #include<bits/stdc++.h>
2019.04.03
下一篇 
[POI2010]GIL-Guilds [POI2010]GIL-Guilds
摘要 之前文化课要准备月考,颓了一会儿 Hexo 博客配置,现在考完了,刷点水题恢复一下 给一张无向图,要求你用黑白灰给点染色,且满足对于任意一个黑点,至少有一个白点和他相邻;对于任意一个白点,至少有一个黑点与他相邻,对于任意一个灰点
2019.04.02
  目录