Hiểu bài toán

Bài toán yêu cầu xác định xem một buổi học có bị hủy hay không dựa trên số lượng học sinh đến đúng giờ. Giáo sư sẽ hủy buổi học nếu số lượng học sinh có mặt trong lớp khi bắt đầu giờ học ít hơn một ngưỡng k cho trước. Dữ liệu đầu vào cung cấp t câu hỏi độc lập. Với mỗi câu hỏi, ta có n học sinh và ngưỡng k. Mỗi học sinh có một số nguyên dương biểu thị thời gian đến lớp; nếu số đó ≤ 0, học sinh đến đúng giờ hoặc sớm, ngược lại nếu > 0 thì đến muộn. Do đó, chỉ cần đếm số lượng học sinh có thời gian ≤ 0, nếu số này nhỏ hơn k thì buổi học bị hủy (YES), ngược lại không hủy (NO).

Các cách tiếp cận

Cách Đếm trực tiếp (Direct Counting)

#include <bits/stdc++.h>
using namespace std;
int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int t;
    cin >> t;
    while (t--) {
        int n, k;
        cin >> n >> k;
        int onTime = 0;
        for (int i = 0; i < n; i++) {
            int x;
            cin >> x;
            if (x <= 0) onTime++;
        }
        if (onTime < k) cout << "YES\n";
        else cout << "NO\n";
    }
    return 0;
}

• Time Complexity: O(n) mỗi câu hỏi, tổng O(t * n)
• Space Complexity: O(1)

Ta chỉ cần đọc từng giá trị thời gian đến lớp, tăng biến đếm onTime nếu giá trị ≤ 0. Sau khi đọc xong n học sinh, so sánh onTime với k. Nếu onTime < k, in YES; ngược lại in NO. Cách này tối ưu và đơn giản nhất.

Cách Lưu mảng và đếm sau (Store Array Then Count)

#include <bits/stdc++.h>
using namespace std;
int main() {
    int t;
    cin >> t;
    int n, k;
    int a[1000];
    int dem = 0;
    for (int i = 1; i <= t; i++) {
        dem = 0;
        cin >> n >> k;
        for (int j = 1; j <= n; j++) {
            cin >> a[j];
            if (a[j] <= 0) dem++;
        }
        if (dem < k) cout << "YES" << endl;
        else cout << "NO" << endl;
    }
    return 0;
}

• Time Complexity: O(n) mỗi câu hỏi
• Space Complexity: O(n) do lưu mảng

Giải pháp này đọc dữ liệu vào mảng trước sau đó mới đếm. Về cơ bản vẫn là O(n) thời gian nhưng tốn thêm bộ nhớ O(n) không cần thiết. Có thể thấy việc lưu mảng không cần thiết vì ta chỉ cần đếm ngay khi đọc.

Cách Brute Force (nếu có thêm ràng buộc phức tạp hơn)

// Không cần thiết do bài đơn giản, nhưng có thể dùng vector hoặc sort nếu cần xử lý thêm.
// Ví dụ nếu câu hỏi yêu cầu tìm số lượng học sinh đến đúng giờ trước một mốc thời gian.
#include <bits/stdc++.h>
using namespace std;
int main() {
    int t;
    cin >> t;
    while (t--) {
        int n, k;
        cin >> n >> k;
        vector<int> a(n);
        for (int i = 0; i < n; i++) cin >> a[i];
        int cnt = 0;
        for (int x : a) if (x <= 0) cnt++;
        cout << (cnt < k ? "YES" : "NO") << "\n";
    }
    return 0;
}

• Time Complexity: O(n)
• Space Complexity: O(n)

Sử dụng vector để lưu trữ, sau đó đếm. Tuy nhiên, đây là cách dùng bộ nhớ lãng phí. Do bài chỉ yêu cầu đếm điều kiện đơn giản, nên dùng phương pháp đếm trực tiếp khi đọc dữ liệu là tốt nhất.

Phân tích độ phức tạp

Bài học kinh nghiệm

• Bài toán chỉ cần kiểm tra số lượng học sinh đến đúng giờ (thời gian ≤ 0) có đủ k hay không.
• Đọc dữ liệu và đếm ngay trong vòng lặp đọc dữ liệu giúp tiết kiệm bộ nhớ và thời gian.

Lỗi thường gặp

• Quên kiểm tra điều kiện '≤ 0' mà chỉ kiểm tra '< 0' dẫn đến sai lệch với trường hợp bằng 0.
• So sánh sai chiều: in 'YES' khi onTime ≥ k thay vì onTime < k.