Codeforces Round #544 (Div. 3) Editorial C. Balanced Team

时间：2019-03-09 10:44:08 阅读：408 评论：0 收藏：0 [点我收藏+]

You are a coach at your local university. There are $n$ students under your supervision, the programming skill of the $i$ -th student is $a_{i}$ .

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$ .

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$ ( $1 \leq n \leq 2 \cdot 10^{5}$ ) — the number of students.

The second line of the input contains $n$ integers $a_{1}, a_{2}, \dots, a_{n}$ ( $1 \leq a_{i} \leq 10^{9}$ ), where $a_{i}$ is a programming skill of the $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

Note

In the first example you can create a team with skills $[12, 17, 15]$ .

In the second example you can take all students in a team because their programming skills are equal.

In the third example you can create a team consisting of a single student (and you cannot create a team consisting of at least two students).

解题思路

　　官方：Let‘s sort all values in non-decreasing order. Then we can use two pointers to calculate for each student

$i$ the maximum number of students $j$ such that $a_{j} - a_{i} \leq 5$ ( $j > i$ ). This is pretty standard approach. We also can use binary search to do it (or we can store for each programming skill the number of students with this skill and just iterate from some skill $x$ to $x + 5$ and sum up all numbers of students).

　　我比赛时用map离散化了一下，又套上桶排，然后才跑双指针……大概是前两题都用到桶，思维被死死限制住了……

源代码

 1 #include<stdio.h>
 2 #include<algorithm>
 3 
 4 int n,k;
 5 
 6 int a[200010];
 7 
 8 int main()
 9 {
10     //freopen("test.in","r",stdin);
11     scanf("%d",&n);
12     for(int i=0;i<n;i++)
13         scanf("%d",a+i);
14     std::sort(a,a+n);
15     int ans=0;
16     int j=0;
17     for(int i=0;i<n;i++)
18     {
19         while(j<n&&a[j]-a[i]<=5)
20         {
21             j++;
22             ans=std::max(j-i,ans);
23         }
24     }
25     printf("%d\n",ans);
26     return 0;
27 }