Hiểu bài toán

Bài toán mô phỏng việc mua vé vào cổng. Có n người xếp hàng tại một quầy vé. Ban đầu, người đầu tiên trong hàng sẽ mua vé và rời hàng. Nếu số vé người đó vừa mua (tức chỉ số thứ tự của họ) lớn hơn một giá trị ngưỡng k, họ sẽ quay lại cuối hàng để mua vé tiếp. Quá trình này lặp lại m lần (tức là tổng cộng có m vé được mua). Yêu cầu: sau khi m vé được bán, in ra số vé mà mỗi người đã mua.

Dữ liệu đầu vào:

• n, k, m: số người, ngưỡng vé, số vé cần bán.
• Mảng a[1..n]: chỉ số thứ tự của mỗi người.

Dữ liệu đầu ra: n số nguyên, số vé mỗi người đã mua.

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

Cách Mô phỏng bằng hàng đợi (Queue)

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

int n, k, m, a[10005], b[10005];
void Solve(){
    cin >> n >> k >> m;
    queue<int> q;
    for(int i = 1; i <= n; ++i){
        cin >> a[i];
        q.push(i);
    }
    while(m--){
        int u = q.front();
        q.pop();
        b[u]++;
        if(a[u] > k) q.push(u);
    }
    for(int i = 1; i <= n; ++i) cout << b[i] << ' ';
}
signed main(){
    ios::sync_with_stdio(0); cin.tie(0);
    freopen("muave.inp", "r", stdin);
    freopen("muave.out", "w", stdout);
    Solve();
    return 0;
}

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

Đây là cách tiếp cận trực quan nhất, mô phỏng chính xác quá trình bán vé. Sử dụng một hàng đợi (queue) để lưu trữ thứ tự những người đang chờ mua vé. Ban đầu, tất cả n người đều ở trong hàng đợi. Trong mỗi bước lặp (tương ứng với một vé được bán):

1. Lấy người đầu tiên (u) ra khỏi hàng đợi.
2. Tăng số vé đã bán của người u lên 1.
3. Kiểm tra điều kiện: nếu chỉ số a[u] lớn hơn k, thì đẩy u vào cuối hàng đợi (tức là họ quay lại cuối hàng).
4. Lặp lại cho đến khi bán đủ m vé. Cách này mô phỏng đúng logic của bài toán.

Cách Tối ưu hóa Logic (Math)

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

int n,k,m,a[1005],res[1005];
vector<int> g;

signed main()
{
    freopen("muave.inp","r",stdin); freopen("muave.out","w",stdout);
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    cin >> n >> k >> m;
    for (int i =1; i <= n; i++)
    {
        cin >> a[i];
    }
    if (m <= n)
    {
        for (int i = 1; i <= n; i++)
        {
            cout << (m>0) << " ";
            m--;
        }
    }
    else
    {
        for (int i = 1; i <= n; i++)
        {
            res[i] = 1;
            if (a[i] > k)
            {
                g.push_back(i);
            }
        }
        m -= n;
        int f = (int)g.size();
        if (f > 0)
        {
            int k = m%f, h = m/f;
            for (int i = 0; i <f; i++)
            {
                res[g[i]] += (k > 0);
                k--;
            }
            for (int i = 0; i < f; i++)
            {
                res[g[i]] += h;
            }
        }
        for (int i = 1; i <= n; i++)
        {
            cout << res[i] << " ";
        }
    }
}

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

Cách tiếp cận này phân tích quy luật thay vì mô phỏng.

1. Vòng lặp đầu tiên: Trong n lần bán đầu tiên, mỗi người chắc chắn mua được 1 vé. Nếu m <= n, kết quả很简单 là m người đầu tiên mua 1 vé, còn lại 0.
2. Vòng lặp tiếp theo: Nếu m > n, sau n lần đầu tiên, người nào có chỉ số a[i] > k sẽ quay lại hàng. Gọi tập hợp này là G (kích thước f).
3. Các lần bán còn lại (m - n vé) sẽ chỉ diễn ra giữa những người trong tập G. Những người này sẽ luân phiên mua vé.
4. Chia m - n cho f (số người trong G). Thương h là số vé thêm mỗi người được mua. Dư k là số người đầu tiên trong tập G được mua thêm 1 vé nữa.
5. Kết quả: res[i] = 1 + h + (i thuộc nhóm đầu của G ? 1 : 0). Cách này tối ưu hơn hẳn về thời gian.

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

Bài học kinh nghiệm

• Vấn đề có thể được chia thành 2 giai đoạn: Giai đoạn 1 (mua vé lần đầu) và Giai đoạn 2 (lặp lại giữa các người đủ điều kiện).
• Nếu chỉ mô phỏng bằng queue, ta có thể xử lý các trường hợp m lớn bằng cách tính toán quy luật chia đều, thay vì lặp m lần.
• Những người không đủ điều kiện (a[i] <= k) chỉ mua được đúng 1 vé và không bao giờ quay lại hàng.

Lỗi thường gặp

• Quên xử lý trường hợp m <= n (số vé ít hơn số người).
• Lầm tưởng rằng người có chỉ số lớn hơn k sẽ mua vé nhiều hơn người khác ngay từ những lượt đầu tiên, trong khi thực tế họ chỉ quay lại sau khi tất cả mọi người (kể cả người không đủ điều kiện) đã mua vé lần đầu.
• Sử dụng mô phỏng queue quá chậm cho m lớn (ví dụ m = 10^9) mà không nhận ra quy luật chia đều.