Hướng dẫn giải của Chọn giày (đề Hòa Bình 2021)


Chỉ dùng lời giải này khi không có ý tưởng, và đừng copy-paste code từ lời giải này. Hãy tôn trọng người ra đề và người viết lời giải.
Nộp một lời giải chính thức trước khi tự giải là một hành động có thể bị ban.

Hướng dẫn giải

Cho n chiếc giày có độ sáng s_i, cần tìm số cặp giày rời nhau tối đa sao cho hai chiếc trong cặp có độ sáng chênh nhau không quá d. Nhận xét: nếu sắp xếp độ sáng tăng dần thì chỉ cần xét các cặp "gần nhau" trong dãy đã sắp xếp.

Sub 1: d = 0 — ~O(n \log n)~

Khi d = 0 chỉ ghép được hai chiếc có cùng độ sáng. Với mỗi nhóm có cnt chiếc bằng nhau, ghép được ~\lfloor cnt/2 \rfloor~ trận. Cộng lại là đáp án.

Nếu chỉ nộp sub này: đúng 1/25 test (chỉ test có d = 0 được tính).

Sub 2: Quy hoạch động — ~O(n^2)~, dùng khi ~n \le 1000~

Sắp xếp dãy, gọi dp[i] là số trận tối đa với i chiếc đầu tiên. Chiếc thứ i hoặc không đấu, khi đó dp[i] = dp[i-1]; hoặc đấu với một chiếc j < i có si - sj \le d, khi đó dp[i] = dp[j-1] + 1 (các chiếc từ j đến i-1 không dùng nữa, vẫn là một cách hợp lệ). Lấy max trên các khả năng.

Nếu chỉ nộp sub 1 và 2 thì đúng mọi test có d > 0 và n <= 1000 (ép chạy riêng sub 2: đúng 20/25 test).

Sub 3: Tham lam — ~O(n \log n)~, dùng cho mọi test

Sau khi sắp xếp, duyệt từ trái sang phải. Nếu chiếc i+1 và chiếc i chênh không quá d thì ghép và chuyển sang i+2; ngược lại bỏ chiếc i và chuyển sang i+1. Lý do: cặp kề nhau là cặp có chênh lệch nhỏ nhất, dùng nó để ghép không làm mất cơ hội ghép của các chiếc còn lại.

Bẫy: d có thể bằng 0 nên cần tách riêng trường hợp này (nhóm bằng nhau), còn tổng số trận có thể tới 10^5 nên dùng long long.

Chương trình hoàn chỉnh

main đọc dữ liệu, sắp xếp độ sáng rồi: d = 0 gọi sub1, n <= 1000 gọi sub2, còn lại gọi sub3. Sub sau có lỗi thì vẫn ăn điểm các sub trước.

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

int n;
long long d;
vector<long long> s;  // độ sáng các chiếc giày, đã sắp xếp tăng dần trong main

// Sub 1: d = 0 — chỉ ghép được hai chiếc có cùng độ sáng. Với mỗi nhóm bằng nhau có cnt chiếc thì ghép được cnt/2 trận.
void sub1() {
    long long ans = 0;
    int i = 0;
    while (i < n) {
        int j = i;
        while (j < n && s[j] == s[i]) j++;
        ans += (j - i) / 2;
        i = j;
    }
    cout << ans << "\n";
}

// Sub 2: quy hoạch động trên dãy đã sắp xếp. dp[i] = số trận tối đa với i chiếc giày đầu tiên.
// Chiếc thứ i hoặc không đấu (dp[i-1]), hoặc đấu với chiếc j < i nào đó có s[i]-s[j] <= d (dp[j-1] + 1). O(n^2). Dùng khi n <= 1000.
void sub2() {
    vector<int> dp(n + 1, 0);  // dp[i] với i chiếc đầu (chỉ số 1..n)
    for (int i = 1; i <= n; i++) {
        dp[i] = dp[i - 1];
        for (int j = 1; j < i; j++)
            if (s[i - 1] - s[j - 1] <= d)
                dp[i] = max(dp[i], dp[j - 1] + 1);
    }
    cout << dp[n] << "\n";
}

// Sub 3: tham lam trên dãy đã sắp xếp. Xét các chiếc liền nhau từ trái sang phải: nếu chiếc i+1 và i chênh không quá d
// thì ghép chúng và bỏ qua cả hai, ngược lại bỏ qua chiếc i. O(n log n) do sắp xếp.
void sub3() {
    long long ans = 0;
    int i = 0;
    while (i + 1 < n) {
        if (s[i + 1] - s[i] <= d) {
            ans++;
            i += 2;
        } else {
            i++;
        }
    }
    cout << ans << "\n";
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cin >> n >> d;
    s.resize(n);
    for (auto &x : s) cin >> x;
    sort(s.begin(), s.end());
    if (d == 0) sub1();        // d = 0: đếm nhóm bằng nhau
    else if (n <= 1000) sub2();  // n vừa: quy hoạch động
    else sub3();               // tham lam
    return 0;
}

Bình luận

Hãy đọc nội quy trước khi bình luận.


Không có bình luận tại thời điểm này.