Hướng dẫn cho Phần thưởng

Chỉ sử dụng khi thực sự cần thiết như một cách tôn trọng tác giả và người viết hướng dẫn này.

Chép code từ bài hướng dẫn để nộp bài là hành vi có thể dẫn đến khóa tài khoản.

Authors: letangphuquy

Subtask \(1\) (\(70\%\) điểm): \(n \le 10^3\).

Tutorial

Phát biểu giống bài toán cái túi. Tuy nhiên, công việc của ta ở đây đơn giản hơn: lấy một món quà đang được chọn, thay bằng một món quà chưa chọn.
Dùng hai vòng for lồng nhau để biết chính xác:

Muốn thay ra ngoài món quà nào?
Muốn thêm vào món quà nào?
Cần tính xem: túi có đủ chứa không? Tổng giá trị sau khi thay là bao nhiêu?
Để việc tính được nhanh, lúc đầu, sau khi nhập vào ta tính luôn túi còn trống bao nhiêu và tổng giá trị hiện tại.
Độ phức tạp: \(\mathcal{O}(n^2)\)

Solution

Trong đoạn code sau, ta bỏ món quà \(i\) và thêm vào món quà \(j\)

C++

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

int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);

    int n, S;
    cin >> n >> S;
    vector<int> w(n), v(n), used(n);
    long long V = 0, ans = 0;
    for (int i = 0; i < n; i++) {
        cin >> w[i] >> v[i] >> used[i];
        if (used[i]) {
            S -= w[i];
            V += v[i];
        }
    }
    ans = V;
    for (int i = 0; i < n; i++) if (used[i])
        for (int j = 0; j < n; j++) if (!used[j]) 
            if (S + w[i] - w[j] >= 0)
                ans = max(ans, V - v[i] + v[j]);
    cout << ans;
}

Subtask \(2\) (\(30\%\) điểm): \(n \le 10^5\).

Tutorial

Chỉ đủ ĐPT thời gian để chạy một vòng for. Vậy ta chỉ biết được là muốn bỏ quà nào. Cần xác định nhanh: thêm vào quà nào khác nữa thì tối ưu?
Giả sử bỏ món quà \(i\), ta biết được ngay chỗ trống hiện tại R += w[i].
Bây giờ, cần tìm trong những món quà \(j\) chưa chọn (\(c = 0\)), thỏa \(w_j \le R\) và \(v_j\) lớn nhất.
Tạo ra một mảng chỉ chứa các món quà chưa chọn. Sau đó, sắp xếp tăng dần theo \(w\). Lúc này, những món quà ta có thể chọn là những món quà nằm ở phần đầu tiên (tiền tố) vì chúng có \(w\) bé nhất.
Cụ thể là bao nhiêu số ở đầu tiên? Có thể dùng TKNP để tính.
Cần tìm \(v \max\) trong số những món quà này? Áp dụng ý tưởng của mảng tiền tố (prefix-sum). Thay vì gán \(f_i = f_{i-1} + a_i\), ta gán \(f_i = \max(f_{i-1}, a_i)\)
Độ phức tạp: \(\mathcal{O}(n \log)\)

Solution

C++

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

void umax(int& var, int val) {
    if (val > var) var = val;
}

int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);

    int n, S;
    cin >> n >> S;
    vector<int> w(n), v(n), used(n);
    vector<pair<int,int>> unused;
    long long V = 0, ans = 0;
    for (int i = 0; i < n; i++) {
        cin >> w[i] >> v[i] >> used[i];
        if (used[i]) {
            S -= w[i];
            V += v[i];
        }
        else unused.push_back({w[i], v[i]});
    }
    ans = V;
    sort(unused.begin(), unused.end());
    int k = unused.size();
    vector<int> prefix_max(k);
    for (int i = 0; i < k; i++) {
        prefix_max[i] = unused[i].second;
        if (i) umax(prefix_max[i], prefix_max[i-1]);
    }
    for (int i = 0; i < n; i++) {
        if (!used[i]) continue;
        S += w[i];
        int pos = -1;
        {
            int low = 0, high = k-1;
            while (low <= high) {
                int mid = (low + high) / 2;
                if (unused[mid].first <= S)
                    pos = mid, low = mid + 1;
                else high = mid-1;
            }
        }
        ans = max(ans, V - v[i] + (pos == -1 ? 0 : prefix_max[pos]));
        S -= w[i];
    }
    cout << ans;
}

Bình luận

Không có bình luận nào.