题解 P3143 【[USACO16OPEN]钻石收藏家Diamond Collector】

· · 题解

本蒟蒻的第一篇题解，求过

看题解都是先预处理再做，那本蒟就来一篇边处理边做的的题解吧。这个方法有点尺取的感觉...

分析题意

题目大意就是要在排好序的数列中找出两段长度和最大的不重合的区间，并使两个区间中的最大值与最小值的差不大于k。

做法

立个 ma 和 r , ma 表示某个位置的左边最多可以取多少颗钻石，放在第一个架子上；r 表示从某个位置向右最多可以延伸到的位置，放在第二个架子上。然后不断枚举位置(i)即可。

参考代码

#include<cstdio>
#include<algorithm>
using namespace std;
int n,k,a[50005],c[50005],r=2,ma,ans;//c[i]用来存从i-1向左最多可以取多少颗钻石。 
int main(){
    scanf("%d %d",&n,&k);
    a[n+1]=2100000000;//立个哨兵，防止r"跑丢"... 
    for(int i=1;i<=n;++i)
        scanf("%d",&a[i]);
    sort(a+1,a+n+1);
    for(int i=1;i<=n;++i){
        while(a[r]<=a[i]+k)r++;//可以往右就尽量往右，因为我们只需要最长的。 
        c[r]=max(r-i,c[r]);
        ma=max(ma,c[i]);//记录第i颗钻石（不包括i）前可以摆最多的钻石。即第一个架子上的钻石。 
        ans=max(ans,ma+r-i);//为什么是'r-i'而不是'c[r]'? 因为要防区间重叠.qwq
    }
    printf("%d",ans);
    return 0;
}