Hiểu bài toán

Bài toán Triển lãm tranh: Có N bức tranh và M khung hình. Mỗi bức tranh i có hai thông số: kích thước (diện tích) Si và giá trị Vi. Mỗi khung hình j có kích thước (diện tích) B_j. Nhiệm vụ là chọn ra một tập hợp các cặp (tranh, khung) sao cho:

1. Mỗi bức tranh chỉ được dùng tối đa 1 lần.
2. Mỗi khung hình chỉ được dùng tối đa 1 lần.
3. Kích thước của bức tranh phải nhỏ hơn hoặc bằng kích thước của khung hình (Si <= Bj). Mục tiêu là tìm số lượng cặp tối đa có thể tạo thành.

Đề bài yêu cầu tối ưu hóa số lượng cặp, có thể được xem là bài toán quy hoạch động hoặc tham lam.

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

Cách Greedy (Sắp xếp giảm dần)

# include <bits/stdc++.h>
using namespace std;
int N,M;
struct picture{
    int s,v;
};
bool compare(picture a,picture b) {
    if (a.v==b.v) return a.s>b.s;
    return a.v>b.v;
}
picture a[100005];
int c[100005];
int main(){
    freopen("picture.inp","r",stdin);
    freopen("picture.out","w",stdout);
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    cin>>N>>M;
    for (int i = 1;i<=N;i++) {
        cin>>a[i].s>>a[i].v;
    }
    for (int i = 1;i<=M;i++) cin>>c[i];
    sort(a+1,a+N+1,compare);
    sort(c+1,c+M+1,greater<int>());
    int j = 1;
    for (int i = 1;i<=N && j<=M;i++) {
        if (a[i].s<=c[j]) j++;
    }
    cout<<j-1;
    return 0;
}

• Time Complexity: O(N log N + M log M)
• Space Complexity: O(N + M)

Cách tiếp cận này sử dụng chiến lược tham lam để tối ưu hóa.

1. Sắp xếp các bức tranh giảm dần theo giá trị (V). Nếu giá trị bằng nhau, sắp xếp giảm dần theo kích thước (S).
2. Sắp xếp các khung hình giảm dần theo kích thước.
3. Duyệt qua các bức tranh từ giá trị cao nhất. Với mỗi bức tranh, ta cố gắng tìm khung hình có kích thước lớn nhất (đứng đầu danh sách khung hình) vừa vặn với nó. Nếu tìm thấy, ta ghép cặp và chuyển sang khung hình tiếp theo (nhỏ hơn). Logic là ưu tiên những bức tranh có giá trị cao nhất và dùng khung hình lớn nhất có thể để giữ lại những khung hình nhỏ hơn cho các bức tranh kém giá trị hơn.

Cách Greedy (Sắp xếp tăng dần)

#include <bits/stdc++.h>
#define int long long
#define N 100000
#define pii pair<int, int>
#define fi first
#define se second
using namespace std;
int n, m;
pair<int, int> a[N + 2];
int b[N + 2];
bool cmp(pii A, pii B)
{
    return A.se == B.se ? A.fi < B.fi : A.se < B.se;
}
int32_t main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(); cout.tie();
    freopen("picture.inp", "r", stdin);
    freopen("picture.out", "w", stdout);
    cin >> n >> m;
    for(int i = 1; i <= n; i++) cin >> a[i].fi >> a[i].se;
    for(int i = 1; i <= m; i++) cin >> b[i];
    sort(b + 1, b + m + 1);
    sort(a + 1, a + n + 1, cmp);
    int cnt = 0;
    int j = m;
    for(int i = n; i >= 1; i--)
    {
        if(j == 0) break;
        if(a[i].fi <= b[j])
        {
            cnt++;
            j--;
        }
    }
    cout << cnt;
    return 0;
}

• Time Complexity: O(N log N + M log M)
• Space Complexity: O(N + M)

Cách tiếp cận này cũng là tham lam nhưng đi ngược lại so với cách trên.

1. Sắp xếp các bức tranh tăng dần theo giá trị (V). Nếu cùng giá trị, sắp xếp tăng dần theo kích thước (S).
2. Sắp xếp các khung hình tăng dần theo kích thước.
3. Duyệt các bức tranh từ cuối danh sách (giá trị cao nhất) về đầu.
4. Duyệt các khung hình từ cuối danh sách (kích thước lớn nhất) về đầu.
5. Nếu kích thước khung hình hiện tại >= kích thước tranh, ta ghép cặp, giảm chỉ số khung hình xuống. Điểm khác biệt chính so với cách 1 là cách xử lý vòng lặp và thứ tự sắp xếp, nhưng về bản chất đều là tìm cách tối ưu hóa số lượng cặp.

Cách Greedy (Sử dụng Multiset)

# include <bits/stdc++.h>
using namespace std;
int N,M;
struct picture{
    int s,v;
};
bool compare(picture a,picture b) {
    if (a.v==b.v) return a.s>b.s;
    return a.v>b.v;
}
picture a[100005];
int c[100005];
int main(){
    freopen("picture.inp","r",stdin);
    freopen("picture.out","w",stdout);
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    cin>>N>>M;
    for (int i = 1;i<=N;i++) {
        cin>>a[i].s>>a[i].v;
    }
    for (int i = 1;i<=M;i++) cin>>c[i];
    sort(a+1,a+N+1,compare);
    sort(c+1,c+M+1);
    // Using multiset for dynamic querying
    multiset<int> frames;
    for(int i=1; i<=M; i++) frames.insert(c[i]);

    int ans = 0;
    for(int i=1; i<=N; i++) {
        auto it = frames.lower_bound(a[i].s);
        if(it != frames.end()) {
            ans++;
            frames.erase(it);
        }
    }
    cout << ans;
    return 0;
}

• Time Complexity: O(N log M)
• Space Complexity: O(M)

Đây là cách tiếp cận linh hoạt hơn.

1. Sắp xếp các bức tranh giảm dần theo giá trị (V).
2. Lưu tất cả các khung hình vào một cấu trúc dữ liệu hiệu quả như Multiset (hoặc C++ Set) để có thể tìm kiếm và xóa phần tử nhanh.
3. Duyệt từng bức tranh (từ giá trị cao nhất). Với mỗi tranh, tìm trong Multiset khung hình có kích thước >= kích thước tranh (sử dụng lower_bound).
4. Nếu tìm thấy, xóa khung hình đó khỏi Multiset và tăng biến đếm. Cách này đảm bảo ta luôn chọn được khung hình phù hợp nhất (vừa vặn nhất) cho mỗi bức tranh mà không cần lo lắng về việc sắp xếp khung hình.

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

Bài học kinh nghiệm

• Bài toán có thể giải được bằng phương pháp tham lam (Greedy).
• Cần ưu tiên các bức tranh có giá trị lớn hơn.
• Với mỗi bức tranh, nên chọn khung hình có kích thước vừa đủ hoặc lớn hơn một chút để tiết kiệm khung hình lớn cho các tranh khác.

Lỗi thường gặp

• Lỗi sắp xếp sai thứ tự (giảm dần/tăng dần) dẫn đến kết quả sai.
• Quên kiểm tra điều kiện biên khi duyệt mảng hoặc sử dụng iterator.
• Sai lệch trong việc ánh xạ dữ liệu (tranh vs khung hình).