题解 P3143 前缀和、two-pointer、贪心
wjyyy
2018-08-30 17:48:57
## 吐槽
解法众多的一道毒瘤题?
### [我的blog](http://www.wjyyy.top/1497.html)
## 题解
其实这个题可以用暴力线段树,也可以用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:
```cpp
#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;
}
```