Problem Description
You are given an integer sequence of length N, a1,a2,…,aN.
For each 1≤i≤N, you have three choices: add 1 to ai, subtract 1 from ai or do nothing.
After these operations, you select an integer X and count the number of i such that ai=X.
Maximize this count by making optimal choices.
Constraints
- 1≤N≤105
- 0≤ai<105(1≤i≤N)
- ai is an integer.
Input
The input is given from Standard Input in the following format:
N
a1 a2 .. aN
Output
Print the maximum possible number of i such that ai=X.Example
Sample Input 1
7
3 1 4 1 5 9 2
Sample Output 1
4
For example, turn the sequence into 2,2,3,2,6,9,2 and select X=2 to obtain 4, the maximum possible count.
Sample Input 2
10
0 1 2 3 4 5 6 7 8 9
Sample Output 2
3
Sample Input 3
1
99999
Sample Output 3
1
題意:給一個長度為 n 的整數序列,對于序列中的每一個數可以進行一次操作,可以對其 +1、-1 或不做任何操作,對這 n 個數進行一次操作後,問序列中次數出現最多的數
思路:由于給出的數 ai 的值不大,可以利用桶排,對于每個數将其 +1、-1、原值均存入桶中,最後掃一遍桶,桶中元素最大值就是答案,需要注意的是,由于 ai 最小可能為 0,将其 -1 後值為 -1,是以桶需要整體向右偏移一個
Source Program
#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<string>
#include<cstring>
#include<cmath>
#include<ctime>
#include<algorithm>
#include<utility>
#include<stack>
#include<queue>
#include<vector>
#include<set>
#include<map>
#include<bitset>
#define EPS 1e-9
#define PI acos(-1.0)
#define INF 0x3f3f3f3f
#define LL long long
const int MOD = 1E9+7;
const int N = 100000+5;
const int dx[] = {-1,1,0,0,-1,-1,1,1};
const int dy[] = {0,0,-1,1,-1,1,-1,1};
using namespace std;
int bucket[N];
int main() {
int n;
scanf("%d",&n);
for(int i=1;i<=n;i++){
int x;
scanf("%d",&x);
x++;//向右偏移
bucket[x]++;
bucket[x-1]++;
bucket[x+1]++;
}
int maxx=-INF;
int res=0;
for(int i=1;i<=1E5+1;i++)
maxx=max(maxx,bucket[i]);
printf("%d\n",maxx);
return 0;
}