定長覆蓋

時間限制：2000?ms ?|? 內(nèi)存限制：65535?KB 難度：2 描述

?

問題很簡單，在一條直線上，坐標從0開始到1000000；現(xiàn)在有n個石子在這條直線上（同一個位置可能有多個石子）

那么用一個定長為m的桿子去覆蓋，請問最多能覆蓋多少個石子？

輸入

輸入有多組數(shù)據(jù)
第一行有2個整數(shù)，n 和 m(n <= 50000,0 < m <= 1000)
第二行有n個整數(shù)代表每個石子的位置(所有的數(shù)小于50000）

輸出

每種情況輸出一個整數(shù)（最多能覆蓋的石子數(shù)）

樣例輸入

3 2 0 0 1 5 2 0 1 2 4 5

樣例輸出

3 3

類似：http://blog.csdn.net/u012804490/article/details/24785835

AC碼：

#include<stdio.h> #include<string.h> int num[50003],sum[50003]; int main() {int n,m,d,i,a;while(~scanf("%d%d",&n,&m)){memset(num,0,sizeof(num));for(i=0;i<n;i++){scanf("%d",&a);num[a]++;}sum[0]=num[0];for(i=1;i<50000;i++){sum[i]=sum[i-1]+num[i];}d=sum[m];for(i=m+1;i<50000;i++){if(d<(sum[i]-sum[i-m-1]))d=sum[i]-sum[i-m-1];}printf("%d\n",d);}return 0; }

總結(jié)

以上是生活随笔為你收集整理的NYOJ 610 定长覆盖的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。