新手启示者
题目描述 Description
贝蒙喜欢闪闪发光的东西，于是有在空闲时间里挖钻石的爱好。她收集了N颗不同大小的钻石（N≤50000），她想在两个漂亮的展示箱里放一些钻石进行展示。因为贝蒙希望展示在同一个箱子里的钻石大小尽量相似，所以她决不会把两颗大小相差超过K的钻石一起放进同一个箱子里（如果两颗钻石的大小恰好相差K那它们也能一起放在同一个箱子里展示）。
给出K，请帮助贝蒙求出她能展示在两个箱子里的钻石数量和的最大值。
输入描述 Input Description
输入的第一行包含N和K(0≤K≤10^9)。
接下来的N行每行包含一个整数表示其中一颗钻石的大小。所有的大小都是正数且不超过10^9。
输出描述 Output Description
输出一个正整数，表示贝蒙能展示的钻石数量的最大值。
注意：一个钻石最多只能放入一个展示箱内。
样例输入 Sample Input
7 3 10 5 1 12 9 5 14
样例输出 Sample Output
5
汪宇航在2021-03-16 19:09:25追加了内容
@谭迪元 @汪恺恒 @张帆@赵逸凡
@李瑞曦
汪宇航在2021-03-18 19:00:55追加了内容
#include <bits/stdc++.h>
using namespace std;
int main(){
int n,k,a[1000000000],b[1000000000],x[1000000000],ans=0;
scanf("%d%d",&n,&k);
for(int i=1;i<=n;i++){
cin>>a[i];
}
for(int i=1;i<=n;i++){
for(int j=i+1;j<=n;j++){
if(a[i]>a[j]){
swap(a[i],a[j]);
}
}
}
for(int i=n,j=n;i>=1;i--){
while(j>=1&&a[i]-a[j]<=k){
j--;
}
b[i]=i-j;
}
for(int i=1,j=1;i<=n;i++){
while(j<=n&&a[j]-a[i]<=k){
j++;
}
x[i]=j-i;
}
for(int i=1;i<=n;i++){
b[i]=max(b[i],b[i-1]);
}
for(int i=n;i>=1;i--){
x[i]=max(x[i],x[i+1]);
}
for(int i=1;i<=n;i++){
ans=max(ans,b[i]+x[i+1]);
}
printf("%d",ans);
return 0;
}
???????????????????????????????????????????????????????????????????????????????????????????
资深光能
const int mxn=51000;
int read(){
int x=0,f=1;
char ch=getchar();
while(ch<'0' || ch>'9'){
if(ch=='-')
f=-1;
ch=getchar();
}
while(ch>='0' && ch<='9'){
x=x*10+ch-'0';
ch=getchar();
}
返回值 x*f;
}
int a[mxn];
int n,k;
int w[mxn],r[mxn];
int main(){
n=read();
k=read();
int i,j;
循环(i=1;i<=n;i++){
a[i]=read();
}
sort(a+1,a+n+1);
int hd=1;
for(i=1;i<=n;i++){
while(a[i]-a[hd]>k)
hd++;
w[i]=max(w[i-1],i-hd+1);
}
hd=n;
for(i=n;i;i--){
while(a[hd]-a[i]>k)
hd--;
r[i]=max(r[i+1],hd-i+1);
}
int ans=0; for(i=1;i<n;i++){
ans=max(ans,w[i]+r[i+1]);
}
printf("%d\n",ans);
资深光能
const int mxn=51000;
int read(){
int x=0,f=1;
char ch=getchar();
while(ch<'0' || ch>'9'){
if(ch=='-')
f=-1;
ch=getchar();
}
while(ch>='0' && ch<='9'){
x=x*10+ch-'0';
ch=getchar();
}
返回值 x*f;
}
int a[mxn];
int n,k;
int w[mxn],r[mxn];
int main(){
n=read();
k=read();
int i,j;
循环(i=1;i<=n;i++){
a[i]=read();
}
sort(a+1,a+n+1);
int hd=1;
for(i=1;i<=n;i++){
while(a[i]-a[hd]>k)
hd++;
w[i]=max(w[i-1],i-hd+1);
}
hd=n;
for(i=n;i;i--){
while(a[hd]-a[i]>k)
hd--;
r[i]=max(r[i+1],hd-i+1);
}
int ans=0; for(i=1;i<n;i++){
ans=max(ans,w[i]+r[i+1]);
}
printf("%d\n",ans);
新手启示者
顶
d=====(￣▽￣*)b
新手启示者
d
中级天翼
其实这题挺难的，
思路大概就是先把钻石按从小到大排序，
然后对于每个点求他前面有多少个差小于k，和后面差小于k，
求法：
for(int i=n,j=n;i>=1;i--){
while(j>=1&&a[i]-a[j]<=k){
j--;
}
frt[i]=i-j;
}
for(int i=1,j=1;i<=n;i++){
while(j<=n&&a[j]-a[i]<=k){
j++;
}
bck[i]=j-i;
}然后任取一点，他前面最大加上后面最大取最大值就是结果了。
for(int i=1;i<=n;i++) frt[i]=max(frt[i],frt[i-1]);
for(int i=n;i>=1;i--) bck[i]=max(bck[i],bck[i+1]);
for(int i=1;i<=n;i++) ans=max(ans,frt[i]+bck[i+1]);
