解法众多的一道毒瘤题？
题目描述
奶牛Bessie很喜欢闪亮亮的东西（Baling~Baling~），所以她喜欢在她的空余时间开采钻石！她现在已经收集了(N)颗不同大小的钻石，现在她想在谷仓的两个陈列架上摆放一些钻石。
Bessie想让这些陈列架上的钻石保持相似的大小，所以她不会把两个大小相差(K)以上的钻石同时放在一个陈列架上（如果两颗钻石的大小差值为(K)，那么它们可以同时放在一个陈列架上）。现在给出(K)，请你帮Bessie确定她最多一共可以放多少颗钻石在这两个陈列架上。
输入输出格式
输入格式：
第一行两个整数(N,K)。
接下来(N)行，每行一个正整数(a_i)，表示第(i)颗钻石的大小。
输出格式：
一行一个正整数，表示Bessie最多能放钻石的数量。输入输出样例
输入样例1：
7 3 10 5 1 12 9 5 14输出样例1：
5
说明对于(100\%)的数据，(Nle50,000,a_ile1,000,000,000, Kle1,000,000,000)。
题解：
其实这个题可以用暴力线段树，也可以用DP单调栈。不过想到一种RMQ方法，也可以完成这道题。
题目要求每个陈列架中的元素最大-最小不超过定值(k)，可以贪心地认为，它们处在一个区间里，下界是一个元素(a_i)，上界是(a_i+k)，这样避免了下界的浪费。同时因为没有顺序的要求，所以可以排序。
而我们要选择两个区间，就得使两个区间并中的元素个数最多。可以考虑用一个数组(f[i])存下以(a[i])开始，长度为(k)的区间有多少个数。
当两个区间不相交的时候，答案肯定就是两个数相加。当两个区间相交的时候呢？我们知道，相交肯定没有不相交优。如果两个区间相交了，可以把稍微靠后的区间向后平移一段，这样不会损失任何区间，反而可能会使答案变优。
所以枚举左边的区间，然后在左区间右端点以右找最大值。可以直接维护后缀最大值来转移，用(mus[i])表示(maxlimits_{jin[i,n]}f[i])，就可以在(O(n))的时间内转移，并在总时间(O(nlog 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
",ans);
return 0;
}