PROBLEM LINK:
Practice
Contest: Division 1
Contest: Division 2
Contest: Division 3
Contest: Division 4
Author: raysh07
Tester: sushil2006
Editorialist: iceknight1093
DIFFICULTY:
Cakewalk
PREREQUISITES:
None
PROBLEM:
N students write an exam, and the i-th receives A_i marks.
Student 1 is Chef.
Find the minimum possible number of students who can pass the exam while ensuring that Chef definitely passes; if the cutoff for passing is chosen optimally.
EXPLANATION:
Since Chef must pass the exam, the cutoff for passing cannot be higher than Chef’s marks.
That is, the cutoff must be \le A_1.
On the other hand, the higher the cutoff, the less number of students who can pass.
So, to minimize the number of passing students, the cutoff should be set as high as possible.
Thus, the optimal choice of cutoff is exactly A_1.
So, the answer is simply the number of students who received \ge A_1 marks, which can be computed in linear time with a simple loop.
TIME COMPLEXITY:
\mathcal{O}(N) per testcase.
CODE:
Editorialist's code (PyPy3)
for _ in range(int(input())):
n = int(input())
a = list(map(int, input().split()))
ans = 0
for x in a:
if x >= a[0]: ans += 1
print(ans)