- http://codeforces.com/contest/1133/problem/C
- time limit per test 2 seconds
- memory limit per test 256 megabytes
- input standard input
- output standard output
- You are a coach at your local university. There are ??n students under your supervision, the programming skill of the ??i-th student is ????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 55.
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≤??≤21051≤n≤2105) - the number of students.
- The second line of the input contains ??n integers ??1,??2,...,????a1,a2,...,an (1≤????≤1091≤ai≤109), where ????ai 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][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
??ithe maximum number of students??jsuch that????−????≤5aj−ai≤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??xto??+5x+5and sum up all numbers of students).
我比赛时用 map 离散化了一下, 又套上桶排, 然后才跑双指针...... 大概是前两题都用到桶, 思维被死死限制住了......
源代码
- #include<stdio.h>
- #include<algorithm>
- int n,k;
- int a[200010];
- int main()
- {
- //freopen("test.in","r",stdin);
- scanf("%d",&n);
- for(int i=0;i<n;i++)
- scanf("%d",a+i);
- std::sort(a,a+n);
- int ans=0;
- int j=0;
- for(int i=0;i<n;i++)
- {
- while(j<n&&a[j]-a[i]<=5)
- {
- j++;
- ans=std::max(j-i,ans);
- }
- }
- printf("%d\n",ans);
- return 0;
- }
- C. Balanced Team
- time limit per test 2 seconds
- memory limit per test 256 megabytes
- input standard input
- output standard output
- You are a coach at your local university. There are ??n students under your supervision, the programming skill of the ??i-th student is ????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 55.
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≤??≤21051≤n≤2105) - the number of students.
- The second line of the input contains ??n integers ??1,??2,...,????a1,a2,...,an (1≤????≤1091≤ai≤109), where ????ai 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][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).
来源: http://www.bubuko.com/infodetail-2981077.html