USACO16OPEN Diamond Collector

题目地址

题解

贪心。
先排序，对于每一个钻石枚举他能到的最长区间，然后看他之前的和他这个区间不相交的最长区间。
统计答案即可，时间复杂度$O(nlogn)$

#include <cstdio>
#include <cstdlib>
#include <algorithm>
#include <cstring>
#include <cctype>
#define INF 2000000000
using namespace std;
typedef long long ll;
int a[100005],n,k,b[100005]={0};
int read(){
    int f=1,x=0;char c=getchar();
    while(c<'0'||c>'9'){if(c=='-')f=-f;c=getchar();}
    while(c>='0'&&c<='9')x=x*10+c-'0',c=getchar();
    return f*x; 
}	
void init(){
    n=read(),k=read();
    for(int i=1;i<=n;i++)
        a[i]=read();
    sort(a+1,a+n+1);
}
void solve(){
    int lst=0,ans=0,maxi=0;
    for(int i=1;i<=n;i++){
        int loc=lower_bound(a+1,a+n+1,a[i]+k+1)-a-i;
        b[i]=loc;
        while(lst+b[lst+1]<i)
            lst++,maxi=max(maxi,b[lst]);
        ans=max(ans,maxi+loc);
    }
    printf("%d\n",ans);
}
int main(){
    init();
    solve();
    return 0;
}