Summary

Given the ceiling heights of the buses and the heights of the students, we want to find the minimum number of uncomfortable students among all valid assignments.

The key point is that there is no capacity limit for the buses, and all students can be assigned to the same bus.

Analysis

A student becomes uncomfortable if their height \(H_j\) is strictly greater than the ceiling height \(D_i\) of their assigned bus, i.e., \(H_j > D_i\).

Here, there is no limit on the number of people on a bus. Also, while students from the same class must be assigned to the same bus, students from different classes can be assigned to the same bus.

This means we can assign all students to the “bus with the tallest ceiling”.

Let the maximum ceiling height of the buses be \(\max D\).

• Students with a height less than or equal to \(\max D\) will not be uncomfortable if assigned to the tallest bus.
• Students with a height strictly greater than \(\max D\) will always be uncomfortable regardless of which bus they take, because their height exceeds the ceiling height of any bus.

Therefore, the answer is the number of students satisfying:

\[ H_j > \max D \]

For example, if the ceiling heights of the buses are \(150, 180, 200\), the height of the tallest bus is \(200\).

In this case, a student of height \(190\) will not be uncomfortable, but a student of height \(210\) will be uncomfortable no matter which bus they take.

Thinking naively about “which bus to assign to each class” makes the problem complicated, but since all students can be assigned to the same bus, it is sufficient to look only at the maximum height.

Algorithm

1. Read all the bus ceiling heights \(D_i\) and find their maximum value \(\max D\).
2. For each student, determine if their height \(H_j\) is greater than \(\max D\).
3. Count the number of students for whom \(H_j > \max D\).
4. Output this count.

The class name \(S_j\) is given as input, but since all students can be assigned to the same bus, it is not used in the calculation of the answer.

Complexity

• Time Complexity: \(O(N + M)\)
• Space Complexity: \(O(1)\)

Implementation Points

Since only the maximum bus height is needed, there is no need to store all the heights in an array.

Also, since \(D_i\) and \(H_j\) are at most \(10^9\), they can fit in a standard 32-bit signed integer (int), but using a 64-bit integer (long long) is safe and prevents any potential overflow issues.

Although you need to read the class names, they are not used in the calculation, so you can simply ignore them after reading.

Source Code

#include <bits/stdc++.h>
using namespace std;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int N, M;
    cin >> N >> M;

    long long maxD = 0;
    for (int i = 0; i < N; i++) {
        long long d;
        cin >> d;
        maxD = max(maxD, d);
    }

    int ans = 0;
    for (int j = 0; j < M; j++) {
        string S;
        long long H;
        cin >> S >> H;
        if (H > maxD) ans++;
    }

    cout << ans << '\n';
    return 0;
}

---

This editorial was generated by gpt-5.5-high.