Phiếu nửa giá (Đề tự luyện HSG Tin 12 – Bài 1)

Nguồn: Đề tự luyện HSG Tin học 12 – Bài 1 (đề tự soạn)Độ khó: DễTham lamSắp xếpMảng cộng dồnTìm kiếm nhị phân

Đề bài

Phiếu nửa giá. Ghe hàng có $N$ món quà, món thứ $i$ giá $p_i$ (mỗi món chỉ có một cái). Mỗi phiếu nửa giá dùng cho đúng một món, món đó chỉ phải trả $\lceil p_i/2 \rceil$; mỗi món dùng nhiều nhất một phiếu, không bắt buộc dùng hết phiếu. Thầy Sơn tính $Q$ phương án, phương án thứ $j$ có $B_j$ nghìn đồng và $M_j$ phiếu. Với mỗi phương án, tính số món nhiều nhất mua được với tổng tiền không vượt quá $B_j$.

Dữ liệu vào: dòng đầu $N, Q$ ($1 \le N, Q \le 2 \cdot 10^5$); dòng hai gồm $p_1, \ldots, p_N$ ($1 \le p_i \le 10^9$); $Q$ dòng sau, mỗi dòng $B_j, M_j$ ($0 \le B_j \le 10^{15}$, $0 \le M_j \le 10^9$).

Kết quả: $Q$ dòng, dòng thứ $j$ là đáp án của phương án thứ $j$.

• Subtask 1 (30%): $N, Q \le 300$.
• Subtask 2 (30%): $N, Q \le 5000$.
• Subtask 3 (40%): không có ràng buộc gì thêm.

Input

6 3
19 12 20 4 28 11
44 1
25 2
85 4

Output

4
3
6

Giải thích

Phương án 1: mua 4 món giá 4, 11, 12, 19, dùng phiếu cho món giá 4: 2 + 11 + 12 + 19 = 44; không thể mua 5 món. Phương án 2: mua 3 món giá 4, 11, 12, dùng phiếu cho món 4 và 11: 2 + 6 + 12 = 20; không thể mua 4 món. Phương án 3: mua cả 6 món, dùng phiếu cho 4 món giá 4, 11, 12, 19: tổng 72 ≤ 85.

Dành cho học viênNộp bài trên ClueOJ

Bạn nào muốn thử nộp bài để hệ thống chấm xem có đúng hay không thì dùng link này nhé. Bộ test có chia subtask và có cả những test "bẫy", nên code đúng ý tưởng nhưng sai chi tiết nhỏ cũng sẽ bị trừ điểm đó.

Nộp bài Phiếu nửa giá

Lời mở đầu

Bài này là bài "khởi động" của đề, nhưng có hai chỗ các bạn phải nghĩ cho chắc trước khi gõ code: mua những món nào và dùng phiếu cho món nào. Mình đi từng bước nhé.

Nhận xét 1 – mua $k$ món thì mua $k$ món rẻ nhất. Giả sử thầy Sơn định mua đúng $k$ món. Nếu trong giỏ có một món giá $x$ mà ngoài ghe còn một món chưa mua giá $y < x$, ta đổi món $x$ lấy món $y$ (phiếu đang dán ở món $x$ thì dán sang món $y$). Cả giá gốc lẫn nửa giá đều không tăng: $y \le x$ và $\lceil y/2 \rceil \le \lceil x/2 \rceil$. Đổi mãi như vậy, giỏ hàng trở thành $k$ món rẻ nhất mà số tiền không tăng.

Nhận xét 2 – phiếu dùng cho các món đắt nhất trong giỏ. Dán phiếu vào món giá $p$ thì tiết kiệm được $p - \lceil p/2 \rceil = \lfloor p/2 \rfloor$ – món càng đắt, tiết kiệm càng nhiều. Dùng thêm phiếu không bao giờ thiệt, nên với $k$ món ta dùng $c = \min(M, k)$ phiếu cho $c$ món đắt nhất trong $k$ món đó.

Hình 1. Phương án 1 của ví dụ ($B = 44$, $M = 1$): bốn món rẻ nhất, phiếu dán vào món 19 – món đắt nhất trong giỏ.

Cẩn thận với ví dụ của đề!

Ở ví dụ, dán phiếu vào món rẻ vẫn mua đủ số món (vì tiền còn dư), nên cách "dùng phiếu cho món rẻ nhất" vẫn ra đúng cả ba dòng. Nhưng thử với hai món giá $2$ và $10$, $B = 7$, $M = 1$: dán phiếu vào món 10 thì trả $2 + 5 = 7$, mua được 2 món; dán vào món 2 thì phải trả $1 + 10 = 11$, chỉ mua được 1 món.

Gọi $\text{cost}(k)$ là số tiền ít nhất để mua $k$ món. Sắp xếp giá tăng dần $p_1 \le p_2 \le \ldots \le p_N$, ta có

$$\text{cost}(k) = \underbrace{p_1 + \cdots + p_{k-c}}_{\text{giá gốc}} + \underbrace{\lceil p_{k-c+1}/2 \rceil + \cdots + \lceil p_k/2 \rceil}_{c\ \text{món dùng phiếu}}, \qquad c = \min(M, k).$$

Đáp án là $k$ lớn nhất có $\text{cost}(k) \le B$. Một điều nữa: tổng giá có thể tới $2 \cdot 10^5 \cdot 10^9 = 2 \cdot 10^{14}$ và $B$ tới $10^{15}$, nên mọi tổng tiền phải dùng long long. Ba cách dưới đây chỉ khác nhau ở tốc độ tính $\text{cost}(k)$.

Cách 1Thử từng k, cộng lại từ đầu · 30%Cách 2Cập nhật tổng khi tăng k · 60%Cách 3Cộng dồn + tìm nhị phân · 100%

Cách 1Thử từng k, cộng lại từ đầu – O(Q·N²) · 30%

Với mỗi phương án, thử $k = 1, 2, \ldots$: cộng lại giá của $k$ món đầu (món ở vị trí $i \ge k - M$ tính nửa giá), nếu vượt $B$ thì dừng. Mỗi lần thử mất $O(k)$, một phương án mất $O(N^2)$, cả bài $O(Q \cdot N^2)$ – khoảng $1{,}4 \cdot 10^7$ phép tính khi $N, Q \le 300$.

Vì sao dừng ngay khi vượt B?

Thêm một món thì $\text{cost}$ không giảm (món mới đắt nhất nhận phiếu, món khác có thể mất phiếu), nên khi $\text{cost}(k) > B$ thì mọi $k$ lớn hơn cũng vượt $B$.

#include <bits/stdc++.h>
using namespace std;
int main() {
    ios::sync_with_stdio(false); cin.tie(nullptr);
    int n, q;
    cin >> n >> q;
    vector<long long> p(n);
    for (int i = 0; i < n; i++) cin >> p[i];
    sort(p.begin(), p.end());
    while (q--) {
        long long B, M;
        cin >> B >> M;
        int ans = 0;
        for (int k = 1; k <= n; k++) {      // thu mua k mon re nhat
            long long cost = 0;
            for (int i = 0; i < k; i++) {
                if (i >= k - M) cost += (p[i] + 1) / 2;   // M mon dat nhat dung phieu
                else cost += p[i];
            }
            if (cost > B) break;
            ans = k;
        }
        cout << ans << "\n";
    }
    return 0;
}

import sys


def main():
    data = sys.stdin.buffer.read().split()
    n, q = int(data[0]), int(data[1])
    p = sorted(map(int, data[2:2 + n]))
    out = []
    pos = 2 + n
    for _ in range(q):
        B = int(data[pos]); M = int(data[pos + 1]); pos += 2
        ans = 0
        for k in range(1, n + 1):          # thu mua k mon re nhat
            cost = 0
            for i in range(k):
                if i >= k - M:
                    cost += (p[i] + 1) // 2  # M mon dat nhat dung phieu
                else:
                    cost += p[i]
            if cost > B:
                break
            ans = k
        out.append(ans)
    sys.stdout.write("\n".join(map(str, out)) + "\n")


main()

Không gian$O(N)$

Thời gian$O(N \log N + Q \cdot N^2)$

Cách 2Cập nhật tổng khi tăng k – O(Q·N) · 60%

Không cần cộng lại từ đầu. Khi đi từ $k-1$ món lên $k$ món:

• món mới $p_k$ là món đắt nhất trong giỏ nên nhận phiếu: cộng thêm $\lceil p_k/2 \rceil$;
• nếu $k > M$, món $p_{k-M}$ không còn nằm trong $M$ món đắt nhất nên mất phiếu: phải trả thêm phần còn lại $p_{k-M} - \lceil p_{k-M}/2 \rceil = \lfloor p_{k-M}/2 \rfloor$.

Chạy tay phương án 1 của đề (giá sau khi sắp xếp: 4, 11, 12, 19, 20, 28; $B = 44$, $M = 1$):

k	Món mới nhận phiếu	Món mất phiếu	cost(k)	≤ 44?
1	⌈4/2⌉ = 2	–	2	có
2	⌈11/2⌉ = 6	món 4: +⌊4/2⌋ = 2	10	có
3	⌈12/2⌉ = 6	món 11: +⌊11/2⌋ = 5	21	có
4	⌈19/2⌉ = 10	món 12: +⌊12/2⌋ = 6	37	có
5	⌈20/2⌉ = 10	món 19: +⌊19/2⌋ = 9	56	không → dừng

Đáp án là 4. Mỗi phương án giờ chỉ mất $O(N)$, cả bài $O(Q \cdot N)$ – khoảng $2{,}5 \cdot 10^7$ khi $N, Q \le 5000$, nhưng tới $4 \cdot 10^{10}$ khi $N, Q = 2 \cdot 10^5$.

#include <bits/stdc++.h>
using namespace std;
int main() {
    ios::sync_with_stdio(false); cin.tie(nullptr);
    int n, q;
    cin >> n >> q;
    vector<long long> p(n + 1);
    for (int i = 1; i <= n; i++) cin >> p[i];
    sort(p.begin() + 1, p.end());
    while (q--) {
        long long B, M;
        cin >> B >> M;
        long long cost = 0;
        int ans = 0;
        for (int k = 1; k <= n; k++) {
            cost += (p[k] + 1) / 2;                  // mon moi dat nhat: dung phieu
            if (k > M) cost += p[k - M] / 2;         // mon k-M mat phieu: tra them phan con lai
            if (cost > B) break;
            ans = k;
        }
        cout << ans << "\n";
    }
    return 0;
}

import sys


def main():
    data = sys.stdin.buffer.read().split()
    n, q = int(data[0]), int(data[1])
    p = [0] + sorted(map(int, data[2:2 + n]))
    out = []
    pos = 2 + n
    for _ in range(q):
        B = int(data[pos]); M = int(data[pos + 1]); pos += 2
        cost = 0
        ans = 0
        for k in range(1, n + 1):
            cost += (p[k] + 1) // 2          # mon moi dat nhat: dung phieu
            if k > M:
                cost += p[k - M] // 2        # mon k-M mat phieu: tra them phan con lai
            if cost > B:
                break
            ans = k
        out.append(ans)
    sys.stdout.write("\n".join(map(str, out)) + "\n")


main()

Không gian$O(N)$

Thời gian$O(N \log N + Q \cdot N)$

Cách 3Mảng cộng dồn + tìm kiếm nhị phân – O((N + Q) log N) · 100%

Công thức $\text{cost}(k)$ gồm hai đoạn liên tiếp của dãy đã sắp xếp: một đoạn tính giá gốc, một đoạn tính nửa giá. Hai đoạn liên tiếp thì tính bằng mảng cộng dồn:

$$P[i] = p_1 + \cdots + p_i, \qquad H[i] = \lceil p_1/2 \rceil + \cdots + \lceil p_i/2 \rceil, \qquad \text{cost}(k) = P[k-c] + H[k] - H[k-c].$$

Giờ mỗi $\text{cost}(k)$ tính trong $O(1)$ với mọi $M$. Và vì $\text{cost}(k)$ không giảm theo $k$ (đã giải thích ở Cách 1), ta tìm kiếm nhị phân $k$ lớn nhất có $\text{cost}(k) \le B$: mỗi phương án chỉ còn $O(\log N)$.

Với ví dụ: $P = [0, 4, 15, 27, 46, 66, 94]$, $H = [0, 2, 8, 14, 24, 34, 48]$. Phương án 1 ($B = 44$, $M = 1$): thử $k = 3$: $P[2] + H[3] - H[2] = 15 + 6 = 21 \le 44$ → lo = 3; thử $k = 5$: $P[4] + H[5] - H[4] = 46 + 10 = 56 > 44$ → hi = 4; thử $k = 4$: $27 + 10 = 37 \le 44$ → lo = 4. Đáp án 4 ✓.

Các bạn tự nhập giá, số tiền, số phiếu để xem tìm kiếm nhị phân chạy nhé:

Giá các món B M

Ví dụ nhanh:

Bẫy thường gặp

• Dùng phiếu cho món rẻ nhất trong giỏ, hoặc cho $M$ món đắt nhất của cả ghe rồi mới chọn món rẻ – cả hai đều ra đúng ví dụ nhưng sai rất nhiều test.
• Quên $c = \min(M, k)$: khi $M > k$ thì chỉ số $k - M$ bị âm. Đề cho $M$ tới $10^9$, lớn hơn cả $N$.
• Dùng int cho mảng cộng dồn hoặc cho $B$: tổng giá tới $2 \cdot 10^{14}$.
• Nửa giá làm tròn lên: $\lceil p/2 \rceil$ = (p + 1) / 2, không phải p / 2.

#include <bits/stdc++.h>
using namespace std;
int main() {
    ios::sync_with_stdio(false); cin.tie(nullptr);
    int n, q;
    cin >> n >> q;
    vector<long long> p(n + 1), P(n + 1, 0), H(n + 1, 0);
    for (int i = 1; i <= n; i++) cin >> p[i];
    sort(p.begin() + 1, p.end());
    for (int i = 1; i <= n; i++) {
        P[i] = P[i - 1] + p[i];             // tong gia goc
        H[i] = H[i - 1] + (p[i] + 1) / 2;   // tong gia nua
    }
    while (q--) {
        long long B, M;
        cin >> B >> M;
        int lo = 0, hi = n;
        while (lo < hi) {
            int k = (lo + hi + 1) / 2;
            int c = (int)min(M, (long long)k);
            long long cost = P[k - c] + H[k] - H[k - c];
            if (cost <= B) lo = k; else hi = k - 1;
        }
        cout << lo << "\n";
    }
    return 0;
}

import sys


def main():
    data = sys.stdin.buffer.read().split()
    n, q = int(data[0]), int(data[1])
    p = sorted(map(int, data[2:2 + n]))
    P = [0] * (n + 1)
    H = [0] * (n + 1)
    s = h = 0
    for i in range(n):
        x = p[i]
        s += x
        h += (x + 1) // 2
        P[i + 1] = s
        H[i + 1] = h
    out = []
    pos = 2 + n
    for _ in range(q):
        B = int(data[pos]); M = int(data[pos + 1]); pos += 2
        lo, hi = 0, n
        while lo < hi:
            k = (lo + hi + 1) >> 1
            c = M if M < k else k
            if P[k - c] + H[k] - H[k - c] <= B:
                lo = k
            else:
                hi = k - 1
        out.append(lo)
    sys.stdout.write("\n".join(map(str, out)) + "\n")


main()

Không gian$O(N)$

Thời gian$O(N \log N + Q \log N)$

C++▶ Chạy tay từng dòng codeTheo dõi mảng p, P, H và hai biến lo, hi khi tìm nhị phân.

Dữ liệu vào (stdin) – sửa thoải mái6 3 19 12 20 4 28 11 44 1 25 2 85 4

Dữ liệu mẫu:

1#include <bits/stdc++.h>

2using namespace std;

3int main() {

4 ios::sync_with_stdio(false); cin.tie(nullptr);

5 int n, q;

6 cin >> n >> q;

7 vector<long long> p(n + 1), P(n + 1, 0), H(n + 1, 0);

8 for (int i = 1; i <= n; i++) cin >> p[i];

9 sort(p.begin() + 1, p.end());

10 for (int i = 1; i <= n; i++) {

11 P[i] = P[i - 1] + p[i]; // tong gia goc

12 H[i] = H[i - 1] + (p[i] + 1) / 2; // tong gia nua

13 }

14 while (q--) {

15 long long B, M;

16 cin >> B >> M;

17 int lo = 0, hi = n;

18 while (lo < hi) {

19 int k = (lo + hi + 1) / 2;

20 int c = (int)min(M, (long long)k);

21 long long cost = P[k - c] + H[k] - H[k - c];

22 if (cost <= B) lo = k; else hi = k - 1;

23 }

24 cout << lo << "\n";

25 }

26 return 0;

27}

ChậmVừaNhanhRất nhanh

Bộ test chấm "bắt" những lỗi nào?

Bộ test có 29 test: 10 test subtask 1 ($N, Q \le 300$), 9 test subtask 2 ($N = Q \approx 5000$), 10 test subtask 3 ($N \approx 2 \cdot 10^5$, $Q = 1{,}5 \cdot 10^5$ đến $1{,}9 \cdot 10^5$). Phần lớn phương án có đáp án lớn (từ $N/2$ đến $N$ món), số tiền $B$ được đặt đúng bằng hoặc thiếu đúng 1 nghìn so với số tiền cần; số phiếu có cả $0$, rất ít, rất nhiều và lớn hơn $N$.

Cách làm	Sub 1 (30%)	Sub 2 (30%)	Sub 3 (40%)	Điểm
Cách 1 – thử từng k, cộng lại từ đầu	Đúng	TLE	TLE	30
Cách 2 – cập nhật tổng khi tăng k	Đúng	Đúng	TLE	60
Cách 3 – cộng dồn + tìm nhị phân	Đúng	Đúng	Đúng	100
Sai 1 – dùng phiếu cho các món rẻ nhất trong giỏ	3/10 test	1/9 test	1/10 test	≈ 16
Sai 2 – mảng cộng dồn kiểu int	3/10 test	1/9 test	2/10 test	≈ 20
Sai 3 – dùng phiếu cho M món đắt nhất cả ghe rồi mới chọn món	3/10 test	1/9 test	TLE/WA	≈ 12

Ghi chú của mình: các cách C++ ở trên đã được chấm thử với đúng bộ test của bài: Cách 1 đúng 10/10 test subtask 1 và chạy quá 3 giây ở mọi test còn lại (đo riêng mất 20–30 giây); Cách 2 đúng hết subtask 1, 2 và quá 3 giây ở mọi test subtask 3; Cách 3 đúng 29/29 test, test lâu nhất khoảng 0,13 giây. Các test mà ba lời giải sai "ăn may" là ví dụ của đề, test chỉ có một món, test mọi món cùng giá $10^9$ (dán phiếu ở đâu cũng như nhau) và test giá rất nhỏ (tổng chưa vượt int).

Rất vui khi anh em nào đã đọc đến những dòng cuối cùng này. Anh em đọc chắc cũng mỏi mắt luôn chứ 😅 vậy anh em nghĩ người viết ra hết đống ở trên còn thế nào nữa 🤪. Vậy nên đừng tiếc gì cho mình một lời bình luận hoặc chia sẻ bài viết để động viên mình nè. Chúc anh em học tốt và gặt hái nhiều thành công 😇