Giao dừa (Đề tự luyện HSG Tin 9 – Bài 2)

Nguồn: Đề tự luyện HSG Tin học 9 – Bài 2 (đề tự soạn)Độ khó: Trung bìnhTham lamSắp xếpPhép chia nguyên

Đề bài

Giao dừa. Có $N$ nhà nằm dọc con kênh về cùng một phía của bến; nhà thứ $i$ cách bến $x_i$ mét và cần nhận đúng $c_i$ trái dừa. Ghe của thầy Sơn chở tối đa $K$ trái mỗi chuyến: xếp dừa ở bến, chạy dọc kênh giao cho một hay nhiều nhà rồi quay về bến. Một nhà có thể nhận dừa trong nhiều chuyến. Riêng chuyến cuối cùng giao xong thì ở lại, không cần về bến. Tính tổng quãng đường ngắn nhất ghe phải chạy.

Dữ liệu vào: dòng 1 gồm $N, K$ $(1 \le N \le 2 \cdot 10^5;\ 1 \le K \le 10^9)$; $N$ dòng sau, mỗi dòng gồm $x_i, c_i$ $(1 \le x_i \le 10^4;\ 1 \le c_i \le 10^9)$.

Kết quả: tổng quãng đường ngắn nhất (mét).

• Subtask 1 (20%): $c_1 + c_2 + \dots + c_N \le 10^6$.
• Subtask 2 (30%): $c_i \le K$ với mọi $i$.
• Subtask 3 (50%): không ràng buộc thêm.

Input

4 3
1100 6
400 3
2000 2
700 3

Output

8600

Giải thích

$K = 3$. Năm chuyến: ($3$ trái cho nhà $1100$ m) $2200$ m; ($1$ trái nhà $700$ m, $2$ trái nhà $1100$ m) $2200$ m; ($1$ trái nhà $400$ m, $2$ trái nhà $700$ m) $1400$ m; ($2$ trái nhà $400$ m) $800$ m; chuyến cuối ($1$ trái nhà $1100$ m, $2$ trái nhà $2000$ m, ở lại) $2000$ m. Tổng $8600$ m.

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 Giao dừa

Lời mở đầu

Đọc đề xong, nhiều bạn sẽ nghĩ ngay tới việc "xếp lịch": chuyến nào chở cho nhà nào, bao nhiêu trái... nghe rất rối. Ta gỡ rối bằng hai nhận xét đơn giản.

Nhận xét 1 – mỗi chuyến chỉ "đáng giá" bằng điểm xa nhất của nó. Ghe chạy trên một đường thẳng, nên một chuyến có về bến dù ghé bao nhiêu nhà thì cũng tốn ít nhất $2f$ mét, với $f$ là khoảng cách tới nhà xa nhất mà chuyến đó ghé; và đúng $2f$ nếu ghe cứ chạy thẳng ra rồi chạy thẳng về, tiện đường thì ghé. Chuyến cuối (không về) tốn $f$ mét. Vậy nếu các chuyến có điểm xa nhất là $f_1 \ge f_2 \ge \dots \ge f_m$ thì tổng quãng đường nhỏ nhất là

$2(f_1 + f_2 + \dots + f_m) - f_1$,

vì ta luôn nên để chuyến xa nhất làm chuyến cuối: nó được "miễn" đoạn về dài nhất.

Nhận xét 2 – trái dừa xa nhất phải đi chung với những trái xa nhì, xa ba... Xếp tất cả các trái dừa theo khoảng cách giảm dần: $p_1 \ge p_2 \ge \dots$ Chuyến chở trái $p_1$ chắc chắn phải chạy tới $p_1$; đã phải chạy xa như thế rồi thì nên chở luôn $K$ trái xa nhất, để những chuyến còn lại đỡ phải đi xa. Cứ thế: chia dãy trái dừa thành từng nhóm $K$ trái liên tiếp, mỗi nhóm là một chuyến.

Hình 1. Mỗi nhóm là một chuyến, chuyến đi tới trái xa nhất (trái đầu tiên) của nhóm. Chuyến tới $2000$ m làm sau cùng nên không phải về.

Vì sao cách chia này tốt nhất? Xét một lịch giao bất kỳ, sắp các chuyến theo điểm xa nhất $f_1 \ge f_2 \ge \dots$ Gộp $j$ chuyến xa nhất lại thì chở được tối đa $jK$ trái, nên trong $jK + 1$ trái xa nhất $p_1, \dots, p_{jK+1}$ phải có ít nhất một trái nằm ở chuyến thứ $j+1$ trở đi. Chuyến đó phải chạy tới ít nhất $p_{jK+1}$, mà nó lại không xa hơn chuyến thứ $j+1$, nên $f_{j+1} \ge p_{jK+1}$. Cộng lại:

$2(f_1 + f_2 + \dots) - f_1 = f_1 + 2(f_2 + f_3 + \dots) \ge p_1 + 2(p_{K+1} + p_{2K+1} + \dots)$,

và vế phải chính là quãng đường của cách chia nhóm ở trên. Vậy không lịch nào tốt hơn được. Đáp án là

$2(p_1 + p_{K+1} + p_{2K+1} + \dots) - p_1$.

Phần còn lại của bài là tính nhanh công thức này khi số trái dừa lên tới $2 \cdot 10^{14}$.

Cách 1Mảng từng trái dừa · 20%Cách 2Mô phỏng từng chuyến · 50%Cách 3Đếm chuyến bằng phép chia · 100%

Cách 1Mảng từng trái dừa – O(S log S) · 20%

Gọi $S = c_1 + c_2 + \dots + c_N$ là tổng số trái dừa. Ở Subtask 1, $S \le 10^6$ nên ta làm đúng như công thức: tạo mảng p chứa vị trí của từng trái dừa (nhà $i$ góp $c_i$ phần tử bằng $x_i$), sắp xếp giảm dần, rồi cộng $2 \cdot p[0] + 2 \cdot p[K] + 2 \cdot p[2K] + \dots$ và trừ đi $p[0]$.

Với ví dụ: p = $2000, 2000, 1100, \mid 1100, 1100, 1100, \mid 1100, 1100, 700, \mid 700, 700, 400, \mid 400, 400$. Các phần tử $p[0], p[3], p[6], p[9], p[12]$ là $2000, 1100, 1100, 700, 400$; tổng $2 \cdot 5300 - 2000 = 8600$.

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

int main() {
    ios::sync_with_stdio(false); cin.tie(nullptr);
    int n; long long K;
    cin >> n >> K;
    vector<long long> p;                       // vi tri cua tung trai dua
    for (int i = 0; i < n; i++) {
        long long x, c;
        cin >> x >> c;
        for (long long j = 0; j < c; j++) p.push_back(x);
    }
    sort(p.begin(), p.end());
    reverse(p.begin(), p.end());               // trai can giao xa nhat dung truoc
    long long ans = 0;
    for (long long i = 0; i < (long long)p.size(); i += K)
        ans += 2 * p[i];                       // chuyen thu i/K di xa nhat toi p[i]
    ans -= p[0];                               // chuyen xa nhat di sau cung, khong quay ve
    cout << ans << "\n";
    return 0;
}

import sys

data = sys.stdin.buffer.read().split()
n = int(data[0]); K = int(data[1])
p = []                                     # vi tri cua tung trai dua
for i in range(n):
    x = int(data[2 + 2 * i]); c = int(data[3 + 2 * i])
    for j in range(c):
        p.append(x)
p.sort(reverse=True)                       # trai can giao xa nhat dung truoc
ans = 0
for i in range(0, len(p), K):
    ans += 2 * p[i]                        # chuyen thu i/K di xa nhat toi p[i]
ans -= p[0]                                # chuyen xa nhat di sau cung, khong quay ve
print(ans)

Không gian$O(S)$

Thời gian$O(S \log S)$

Đừng quên long long

Ngay cả ở Subtask 1, đáp án đã có thể vượt $2^{31}$: một nhà cách $10^4$ m cần $10^6$ trái, $K = 1$ thì ghe chạy gần $2 \cdot 10^{10}$ m. Biến ans phải là long long.

Vì sao không chạy được Subtask 2, 3?

Khi $c_i$ lên tới $10^9$ thì $S$ có thể tới $2 \cdot 10^{14}$ trái — mảng p cần hàng trăm nghìn GB bộ nhớ. Ta phải làm việc với từng nhà thay vì từng trái.

Cách 2Mô phỏng từng chuyến – O(N log N + số chuyến) · 50%

Thay vì bung từng trái, ta sắp các nhà theo $x$ giảm dần và cho ghe chạy từng chuyến: chuyến mới luôn đi tới nhà xa nhất còn thiếu dừa (cộng $2x$ vào đáp án), rồi lần lượt "đổ" dừa cho nhà đó, hết chỗ thì thôi, nhà đó đủ rồi mà ghe còn chỗ thì đổ tiếp cho nhà gần hơn kế tiếp. Đây đúng là cách chia nhóm $K$ trái liên tiếp ở trên, chỉ là mỗi lần xử lý cả một khúc trái dừa cùng nhà.

Mỗi vòng lặp trong hoặc làm một nhà đủ dừa (i++, tối đa $N$ lần) hoặc làm ghe hết chỗ (kết thúc chuyến), nên tổng số bước là $O(N + \text{số chuyến})$. Ở Subtask 2, mỗi $c_i \le K$ nên số chuyến $\lceil S / K \rceil \le N$: chương trình chạy rất nhanh.

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

int main() {
    ios::sync_with_stdio(false); cin.tie(nullptr);
    int n; long long K;
    cin >> n >> K;
    vector<pair<long long, long long>> h(n);      // (khoang cach x, so trai con phai giao)
    for (int i = 0; i < n; i++) cin >> h[i].first >> h[i].second;
    sort(h.begin(), h.end());
    reverse(h.begin(), h.end());                  // nha xa nhat dung truoc
    long long ans = 0;
    int i = 0;
    while (i < n) {                               // moi vong lap la mot chuyen ghe
        ans += 2 * h[i].first;                    // chuyen nay di xa nhat toi nha i
        long long cho = K;                        // so cho trong tren ghe
        while (cho > 0 && i < n) {
            long long g = min(cho, h[i].second);  // giao cho nha i nhieu nhat co the
            h[i].second -= g; cho -= g;
            if (h[i].second == 0) i++;            // nha i da du dua
        }
    }
    ans -= h[0].first;                            // chuyen toi nha xa nhat di sau cung, khong quay ve
    cout << ans << "\n";
    return 0;
}

import sys

data = sys.stdin.buffer.read().split()
n = int(data[0]); K = int(data[1])
h = []
for i in range(n):
    h.append([int(data[2 + 2 * i]), int(data[3 + 2 * i])])   # [khoang cach x, so trai con phai giao]
h.sort(reverse=True)                                         # nha xa nhat dung truoc
ans = 0
i = 0
while i < n:                       # moi vong lap la mot chuyen ghe
    ans += 2 * h[i][0]             # chuyen nay di xa nhat toi nha i
    cho = K                        # so cho trong tren ghe
    while cho > 0 and i < n:
        g = min(cho, h[i][1])      # giao cho nha i nhieu nhat co the
        h[i][1] -= g; cho -= g
        if h[i][1] == 0:
            i += 1                 # nha i da du dua
ans -= h[0][0]                     # chuyen toi nha xa nhat di sau cung, khong quay ve
print(ans)

Không gian$O(N)$

Thời gian$O(N \log N + \text{số chuyến})$

Vì sao không chạy được Subtask 3?

Khi $K$ nhỏ còn $c_i$ lớn, số chuyến khổng lồ: ví dụ $K = 1000$, tổng $S \approx 10^{14}$ trái thì có khoảng $10^{11}$ chuyến. Mô phỏng từng chuyến chắc chắn quá thời gian. Nhưng để ý: khi ghe đang ở một nhà còn rất nhiều dừa, các chuyến liên tiếp tới nhà đó giống hệt nhau — ta đếm chúng bằng một phép chia là xong!

Cách 3Đếm số chuyến bằng phép chia – O(N log N) · 100%

Duyệt các nhà theo $x$ giảm dần và giữ biến du = số chỗ còn trống trên những chuyến đã chạy tới chỗ xa hơn (chuyến cuối cùng đã mở thường chưa chở đầy). Đến nhà $(x, c)$:

• Nếu du $\ge c$: các chuyến cũ chở kèm đủ dừa cho nhà này, không tốn thêm mét nào. Giảm du đi $c$.
• Ngược lại: chở kèm được du trái, còn thiếu $c' = c - du$ trái. Phải mở thêm $t = \lceil c' / K \rceil$ chuyến mới tới đúng nhà này, tốn $2 \cdot x \cdot t$ mét, và chuyến mới cuối cùng còn trống $du = t \cdot K - c'$ chỗ để chở kèm cho các nhà gần hơn.

Cuối cùng trừ đi $x$ của nhà xa nhất (chuyến đó làm sau cùng, không về). Trong C++, $\lceil a / b \rceil$ với số nguyên dương viết là (a + b - 1) / b.

Với ví dụ ($K = 3$): nhà $2000$ cần $2$ → $t = 1$, cộng $4000$, $du = 1$. Nhà $1100$ cần $6$, chở kèm $1$, thiếu $5$ → $t = 2$, cộng $4400$, $du = 1$. Nhà $700$ cần $3$, kèm $1$, thiếu $2$ → $t = 1$, cộng $1400$, $du = 1$. Nhà $400$ cần $3$, kèm $1$, thiếu $2$ → $t = 1$, cộng $800$, $du = 1$. Tổng $10600 - 2000 = 8600$. Các em bấm thử mô phỏng dưới đây nhé.

K Khoảng cách x Số trái c

Ví dụ nhanh:

Mỗi nhà xử lý trong $O(1)$, nên thời gian chủ yếu nằm ở bước sắp xếp.

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

int main() {
    ios::sync_with_stdio(false); cin.tie(nullptr);
    int n; long long K;
    cin >> n >> K;
    vector<pair<long long, long long>> h(n);      // (khoang cach x, so trai c)
    for (int i = 0; i < n; i++) cin >> h[i].first >> h[i].second;
    sort(h.begin(), h.end());
    reverse(h.begin(), h.end());                  // nha xa nhat dung truoc
    long long ans = 0, du = 0;                    // du = cho trong con lai cua cac chuyen da di xa hon
    for (int i = 0; i < n; i++) {
        long long x = h[i].first, c = h[i].second;
        if (du >= c) { du -= c; continue; }       // cac chuyen truoc cho ke luon
        c -= du;
        long long t = (c + K - 1) / K;            // so chuyen moi phai di toi x
        ans += 2 * x * t;
        du = t * K - c;
    }
    ans -= h[0].first;                            // chuyen toi nha xa nhat di sau cung, khong quay ve
    cout << ans << "\n";
    return 0;
}

import sys

def main():
    data = sys.stdin.buffer.read().split()
    n = int(data[0]); K = int(data[1])
    h = [0] * n
    for i in range(n):
        h[i] = (int(data[2 + 2 * i]) << 30) | int(data[3 + 2 * i])   # ghep (x, c) thanh mot so de sap xep nhanh
    h.sort(reverse=True)                                              # nha xa nhat dung truoc
    M = (1 << 30) - 1
    ans = 0; du = 0
    for v in h:
        x = v >> 30; c = v & M
        if du >= c:
            du -= c
            continue
        c -= du
        t = (c + K - 1) // K
        ans += 2 * x * t
        du = t * K - c
    ans -= h[0] >> 30
    sys.stdout.write(str(ans) + "\n")

main()

Không gian$O(N)$

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

C++▶ Chạy tay từng dòng codeSắp nhà từ xa về gần, dùng du để chở kèm và đếm số chuyến mới bằng phép chia.

Dữ liệu vào (stdin) – sửa thoải mái4 3 1100 6 400 3 2000 2 700 3

Dữ liệu mẫu:

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

2using namespace std;

3

4int main() {

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

6 int n; long long K;

7 cin >> n >> K;

8 vector<pair<long long, long long>> h(n); // (khoang cach x, so trai c)

9 for (int i = 0; i < n; i++) cin >> h[i].first >> h[i].second;

10 sort(h.begin(), h.end());

11 reverse(h.begin(), h.end()); // nha xa nhat dung truoc

12 long long ans = 0, du = 0; // du = cho trong con lai cua cac chuyen da di xa hon

13 for (int i = 0; i < n; i++) {

14 long long x = h[i].first, c = h[i].second;

15 if (du >= c) { du -= c; continue; } // cac chuyen truoc cho ke luon

16 c -= du;

17 long long t = (c + K - 1) / K; // so chuyen moi phai di toi x

18 ans += 2 * x * t;

19 du = t * K - c;

20 }

21 ans -= h[0].first; // chuyen toi nha xa nhat di sau cung, khong quay ve

22 cout << ans << "\n";

23 return 0;

24}

ChậmVừaNhanhRất nhanh

Ba cái bẫy hay gặp

(1) Tính riêng từng nhà $\lceil c_i / K \rceil$ chuyến, quên rằng chuyến đi xa còn trống chỗ có thể chở kèm cho nhà gần hơn. (2) Cho chuyến cuối cùng trong vòng lặp (tức chuyến gần nhất) là chuyến không về — phải là chuyến xa nhất mới tiết kiệm nhiều nhất. (3) Tràn số: $t$ có thể tới $10^9$ và $x$ tới $10^4$, nên 2 * x * t phải tính bằng long long (đáp án lớn nhất gần $4 \cdot 10^{18}$, vẫn vừa long long).

Còn xếp dừa cho nhà gần trước thì sao?

Nếu nhóm $K$ trái từ gần ra xa, nhóm cuối (xa nhất) có thể chỉ có vài trái mà vẫn phải chạy tới tận nhà xa nhất, còn các nhóm khác lại bị kéo ra xa hơn cần thiết. Ví dụ $K = 2$, nhà $10$ m cần $1$ trái, nhà $100$ m cần $2$ trái: nhóm từ xa cho $2 \cdot 100 + 2 \cdot 10 - 100 = 120$ m, còn nhóm từ gần cho $2 \cdot 100 + 2 \cdot 100 - 100 = 300$ m.

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

Bộ test có 30 test: Subtask 1 có 10 test (tổng số trái $\le 10^6$; gồm ví dụ, $N = 1$, $K = 1$, $K = 10^9$, mọi nhà cùng vị trí, $N = 2 \cdot 10^5$), Subtask 2 có 9 test ($N \approx 2 \cdot 10^5$, $c_i \le K$, $K$ từ $10^5$ tới $10^9$, tổng số trái từ $10^{10}$ tới $1{,}45 \cdot 10^{14}$), Subtask 3 có 11 test ($N \approx 2 \cdot 10^5$, $c_i$ tới $10^9$, $K$ từ $1$ tới $9999$, mọi test cần ít nhất $10^{10}$ chuyến; có test đáp án gần $4 \cdot 10^{18}$). Điểm tính theo từng test (thang 100%).

Cách làm	Sub 1 (10 test)	Sub 2 (9 test)	Sub 3 (11 test)	Điểm
Cách 1 – Mảng từng trái dừa	Đúng 10/10	MLE 0/9	MLE 0/11	20
Cách 2 – Mô phỏng từng chuyến	Đúng 10/10	Đúng 9/9	TLE 0/11	50
Cách 3 – Đếm chuyến bằng phép chia (chuẩn)	Đúng 10/10	Đúng 9/9	Đúng 11/11	100
Sai: dùng int, 2 * x * t bị tràn	WA 9/10	Đúng 9/9	WA 2/11	57,1
Sai: xếp dừa cho nhà gần trước	WA 7/10	WA 0/9	WA 3/11	27,6
Sai: tính riêng từng nhà, không chở kèm	WA 4/10	WA 0/9	WA 2/11	17,1
Sai: chuyến gần nhất mới là chuyến không về	WA 4/10	WA 0/9	WA 1/11	12,5

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à hết bộ nhớ ở toàn bộ 20 test còn lại (mảng từng trái dừa quá lớn); Cách 2 đúng 19/19 test của hai subtask đầu và quá thời gian (hơn 3 giây) ở cả 11 test Subtask 3; Cách 3 đúng 30/30 test, test lâu nhất chạy khoảng 0,06 giây. Lời giải Python của Cách 3 cũng đúng 30/30 test, chạy tối đa khoảng 0,2 giây với CPython. Ví dụ của đề khá "hiền": số chuyến tới mỗi nhà tình cờ vẫn bằng $\lceil c_i / K \rceil$ và nhóm từ gần ra xa cũng tình cờ ra cùng kết quả, nên lời giải "tính riêng từng nhà", lời giải "xếp nhà gần trước" và lời giải tràn số đều vẫn ra đúng $8600$ — nhớ tự nghĩ thêm test nha!

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 😇