You are a coach at your local university. There are n n students under your supervision, the programming skill of the i i -th student is a i ai . You have to create a team for a new programming competition. As you know, the more students some team has the more probable its victory is! So you have to create a team with the maximum number of students. But you also know that a team should be balanced. It means that the programming skill of each pair of students in a created team should differ by no more than 5 5 . Your task is to report the maximum possible number of students in a balanced team. Input The first line of the input contains one integer n n ( 1≤n≤2⋅ 10 5 1≤n≤2⋅105 ) — the number of students. The second line of the input contains n n integers a 1 , a 2 ,…, a n a1,a2,…,an ( 1≤ a i ≤ 10 9 1≤ai≤109 ), where a i ai is a programming skill of the i i -th student. Output Print one integer — the maximum possible number of students in a balanced team. Examples Input Copy 6 1 10 17 12 15 2 Output Copy 3 Input Copy 10 1337 1337 1337 1337 1337 1337 1337 1337 1337 1337 Output Copy 10 Input Copy 6 1 1000 10000 10 100 1000000000 Output Copy 1 #####题解:题意给n个数,求子集的最小值和最大值之差不超过5,求最大的子集的元素数. #####我的思路:先对数组排序,这里如果直接暴力的话,O(n^2)的复杂度,肯定会tle, #####优化一下,因为是排过序的,所以子集的左端和右端都是极值,如果右值与左值之差大于5,左值的位置右移, ####再次优化,如果前一值与后一值之差大于5,I 移动的后一值的位置.
1#include <bits/stdc++.h> 2const int N=2e5+5; 3using namespace std; 4int a[N],b[N]; 5int ans=0,cnt=0,flag=0,maxn=0; 6void check(int m){ 7 if(m>maxn) maxn=m; 8} 9int cal(int i,int j){ 10 return a[j]-a[i]; 11} 12int main(){ 13 int n; 14 scanf("%d",&n); 15 for(int i=1;i<=n;i++){ 16 scanf("%d",&a[i]); 17 } 18 sort(a+1,a+1+n); 19 int i=1,j=i+1; 20 while(i<=n-1&&j<=n){ 21 if(cal(j-1,j)>5){ 22 check(j-1-i); 23 i=j; 24 j++; 25 } 26 else if(cal(i,j)>5){ 27 check(j-1-i); 28 i++; 29 if(i==j) j++; 30 //cout<<"jjg"<<endl; 31 } 32 else{ 33 j++; 34 //cout<<"jj"<<endl; 35 } 36 //if(!flag) break; 37 } 38 check(j-1-i); 39 printf("%d\n",maxn+1); 40 return 0; 41}