nyist 610 定长覆盖

定长覆盖

时间限制：2000 ms | 内存限制：65535 KB

难度：2

描述

问题很简单，在一条直线上，坐标从0开始到1000000；现在有n个石子在这条直线上（同一个位置可能有多个石子）

那么用一个定长为m的杆子去覆盖，请问最多能覆盖多少个石子？

输入

输入有多组数据
第一行有2个整数，n 和 m(n <= 50000,m <= 1000)
第二行有n个整数代表每个石子的位置(所有的数小于50000）

输出

每种情况输出一个整数（最多能覆盖的石子数）

样例输入

样例输出

3

3

首先求0--m的和值，然后进行加后减前，就是把后面一个的加上，把最前面的那个删除
a[1--m+1] = a[0--m] + a[m+1]- a[0];

 1 #include <cstdio>
 2 #include<cstring>
 3 #include <algorithm>
 4 
 5 using namespace std;
 6 
 7 int a[1000005];
 8 
 9 int main()
10 {
11     int n,m;
12     while(scanf("%d%d",&n,&m) != EOF)
13      {
14          memset(a,0,sizeof(a));
15 
16          int i;
17          int max = 0;
18          int t = 0;
19          for(i = 0; i < n; i++)
20            {
21                scanf("%d",&t);
22                a[t]++;
23                if(max < t) max = t;
24            }
25         if(max <= m)
26           {
27               printf("%d\n\n",n);
28               continue;
29           }
30 
31         int j;
32         int sum = 0;
33         for(i = 0; i <= m;i++)
34            sum += a[i];
35         int max_sum = sum;
36         for(; i <= max; i++)
37          {
38              sum+=a[i];
39              sum -= a[i-m-1];
40              if(max_sum < sum)
41                max_sum = sum;
42          }
43          printf("%d\n\n",max_sum);
44      }
45      return 0;
46 }