AT_abc473_c.Change Schools
入门
通过率:0%
时间限制:2.00s
内存限制:1024MB
AC君温馨提醒
该题目为【atcoder】题库的题目,您提交的代码将被提交至atcoder进行远程评测,并由ACGO抓取测评结果后进行展示。由于远程测评的测评机由其他平台提供,我们无法保证该服务的稳定性,若提交后无反应,请等待一段时间后再进行重试。
题目描述
Currently, AtCoder High School has K classes and N students, and the i-th (1≤i≤N) student belongs to the Ai-th class.
Takahashi is transferring to AtCoder High School in September. At that time, he can choose any one class among the K classes and belong to that class.
He will be sad if there is a class with more students belonging to it than the class he belongs to. Otherwise, he will be happy.
Find how many classes make him happy if he belongs to them.
目前,AtCoder 高中一共有 K 个班级和 N 名学生,其中第 i 名学生 (1≤i≤N) 属于第 Ai 个班级。
高桥将于九月转入 AtCoder 高中。届时,他可以从 K 个班级中任选一个加入。
如果存在某个班级的学生人数严格多于他所加入的班级的学生人数,则他会感到悲伤;否则,他会感到开心。
求出有多少个班级,使得他加入该班级后会感到开心。
输入格式
The input is given from Standard Input in the following format:
N K
A1 A2 … AN
输入从标准输入中按以下格式给出:
N K
A1 A2 … AN
输出格式
Output the number of classes satisfying the condition.
输出满足条件的班级数量。
输入输出样例
输入#1
8 5 3 3 5 5 4 4 3 2
输出#1
3
输入#2
6 1 1 1 1 1 1 1
输出#2
1
输入#3
14 8 6 1 5 3 8 4 3 4 3 5 1 2 5 1
输出#3
4
说明/提示
Sample 1 Explanation:
For example, if Takahashi chooses the fifth class and belongs to it, the number of students belonging to the fifth class becomes 3. Then, he will be happy since there is no class with more than three students belonging to it.
On the other hand, for example, if he chooses the first class and belongs to it, the number of students belonging to the first class becomes 1. Then, he will be sad since three students belong to the third class.
He will be happy if and only if he chooses the third, fourth, or fifth class, so output 3.
Sample 2 Explanation:
It is possible that AtCoder High School has only one class.
Constraints
- 1≤N≤2×105
- 1≤K≤N
- 1≤Ai≤K (1≤i≤N)
- All input values are integers.
样例 1 解释:
例如,若高桥选择加入第五个班级,则第五个班级的学生人数变为 3。此时他将感到开心,因为没有任何一个班级的学生人数超过 3 人。
另一方面,例如,若他选择加入第一个班级,则第一个班级的学生人数变为 1。此时他将感到不开心,因为第三个班级有 3 名学生。
当且仅当他选择加入第三个、第四个或第五个班级时,他才会感到开心,因此输出 3。
样例 2 解释:
AtCoder 高中可能仅有一个班级。
约束条件
- 1≤N≤2×105
- 1≤K≤N
- 1≤Ai≤K (1≤i≤N)
- 所有输入值均为整数。
输入解题思路,AI测评打分。不知道怎么写?