NC24294. [USACO 2016 Ope B]Diamond Collector
描述
输入描述
The first line of the input file contains N and K (0≤K≤10,000). The next N lines each contain an integer giving the size of one of the diamonds. All sizes will be positive and will not exceed 10,000.
输出描述
Output a single positive integer, telling the maximum number of diamonds that Bessie can showcase.
示例1
输入:
5 3 1 6 4 3 1
输出:
4
C++14(g++5.4) 解法, 执行用时: 4ms, 内存消耗: 928K, 提交时间: 2020-08-06 10:42:46
#include <bits/stdc++.h>
using namespace std;
const int maxn=4e5+7;
const int INF=0x3f3f3f3f;
const int T=1e4+1;
int a[maxn];
map<int,int>op;
int sum[maxn];
signed main()
{
int n,k;
scanf("%d%d",&n,&k);
for(int i=1;i<=n;++i)
{
scanf("%d",a+i);
++op[a[i]];
}
int ans=0;
for (int i=1;i<T;++i)sum[i]=sum[i-1]+op[i];
for (int i=1;i<=T-k;++i)ans=max(ans,sum[i+k]-sum[i-1]);
printf("%d\n",ans);
return 0;
}
C++11(clang++ 3.9) 解法, 执行用时: 3ms, 内存消耗: 492K, 提交时间: 2020-08-07 09:06:58
#include<bits/stdc++.h>
using namespace std;
int main()
{
int n,k,s[1010],j=0,c=0,m=0;
cin>>n>>k;
for(int i=0;i<n;i++)cin>>s[i];
sort(s,s+n);
for(int i=0;i<n;i++){while(s[i]-s[j]>k)j++,c--;c++;m=max(m,c);}
cout<<m;
return 0;
}