题解 P3143 前缀和、two-pointer、贪心

· · 题解

吐槽

   解法众多的一道毒瘤题？

我的blog

题解

   其实这个题可以用暴力线段树，也可以用DP单调栈。不过想到一种RMQ方法，也可以完成这道题。

   题目要求每个陈列架中的元素最大-最小不超过定值k，可以贪心地认为，它们处在一个区间里，下界是一个元素a_i，上界是a_i+k，这样避免了下界的浪费。同时因为没有顺序的要求，所以可以排序。

   而我们要选择两个区间，就得使两个区间并中的元素个数最多。可以考虑用一个数组f[i]存下以a[i]开始，长度为k的区间有多少个数。

   当两个区间不相交的时候，答案肯定就是两个数相加。当两个区间相交的时候呢？我们知道，相交肯定没有不相交优。如果两个区间相交了，可以把稍微靠后的区间向后平移一段，这样不会损失任何区间，反而可能会使答案变优。

   所以枚举左边的区间，然后在左区间右端点以右找最大值。可以直接维护后缀最大值来转移，用mus[i]表示\max\limits_{j\in[i,n]}f[i]，就可以在O(n)的时间内转移，并在总时间O(n\log n)内完成全部过程。

Code：

#include<cstdio>
#include<cstring>
#include<algorithm>
int mus[51000];//后缀最大值
int a[51000];
int b[51000];
int main()
{
    int n,k;
    scanf("%d%d",&n,&k);
    for(int i=1;i<=n;++i)
        scanf("%d",&b[i]);
    std::sort(b+1,b+1+n);
    int t1=n;
    for(int i=n;i;--i)
    {
        while(b[t1]>b[i]+k)
            --t1;
        a[i]=t1-i+1;//用two-pointer统计上界
        mus[i]=std::max(mus[i+1],a[i]);
    }

    int ans=0;
    for(int i=1;i<=n;++i)
    {
        int ans1=0;
        ans1=mus[i+a[i]];//转移最大值
        ans=std::max(ans,a[i]+ans1);
    }
    printf("%d\n",ans);
    return 0;
}