Descrirption
给你一个长度为 \(n\) 的序列,求将它分成两个序列后最多个数,每个序列最大值最小值不能超过 \(k\)
Sol
二分+DP.
排一下序,找出以这个点结尾和开始的位置.
这个玩意可以二分也可以用单调队列,随便搞啊...
然后统计答案就是枚举第二个序列的起点,然后往后扫的时候统计一下,第一个序列的最大长度就可以了.
Code
/**************************************************************
Problem: 4582
User: BeiYu
Language: C++
Result: Accepted
Time:76 ms
Memory:1876 kb
****************************************************************/ #include <cstdio>
#include <algorithm>
#include <iostream>
using namespace std; const int N =50050; int n,k,ans;
int a[N];
int f[N],g[N]; inline int in(int x=0){ scanf("%d",&x);return x; }
int uppp(int x){// >=
int l=1,r=n,mid;
for(;l<=r;){
mid=(l+r)>>1;
if(a[mid] < x) l=mid+1;
else r=mid-1;
}return l;
}
int lwww(int x){//<=
int l=1,r=n,mid;
for(;l<=r;){
mid=(l+r)>>1;
if(a[mid] <= x) l=mid+1;
else r=mid-1;
}return r;
}
int main(){
n=in(),k=in();
for(int i=1;i<=n;i++) a[i]=in();
sort(a+1,a+n+1); for(int i=1;i<=n;i++){
f[i]=i-uppp(a[i]-k)+1;
g[i]=lwww(a[i]+k)-i+1;
} // for(int i=1;i<=n;i++) cout<<a[i]<<" ";cout<<endl;
// for(int i=1;i<=n;i++) cout<<f[i]<<" ";cout<<endl;
// for(int i=1;i<=n;i++) cout<<g[i]<<" ";cout<<endl; for(int i=1;i<=n;i++){
ans=max(ans,f[i-1]+g[i]);
f[i]=max(f[i],f[i-1]);
}
cout<<ans<<endl;
return 0;
}