Hai bến đò (Đề 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ìnhSắp xếpTrung vị có trọng sốTổng tiền tố

Đề bài

Hai bến đò. Có $N$ xóm dọc bờ sông (một trục số), xóm $i$ ở vị trí $x_i$ và có $w_i$ người. Thầy Sơn xây đúng hai bến đò ở hai vị trí nguyên $P, Q$ (có thể trùng nhau); mỗi người đi tới bến gần mình hơn. Tìm giá trị nhỏ nhất của

$$S = \sum_{i=1}^{N} w_i \cdot \min(|x_i - P|,\ |x_i - Q|).$$

Dữ liệu vào: dòng 1 là $N$ $(1 \le N \le 2\cdot 10^5)$; $N$ dòng sau, mỗi dòng $x_i, w_i$ $(0 \le x_i \le 10^9,\ 1 \le w_i \le 10^4)$, không nhất thiết theo thứ tự vị trí.

Kết quả: giá trị $S$ nhỏ nhất.

• Subtask 1 (20%): $N \le 100$.
• Subtask 2 (30%): $N \le 5000$.
• Subtask 3 (50%): không ràng buộc thêm.

Input

7
3 1
8 9
12 3
13 7
27 4
30 7
34 4

Output

80

Giải thích

Bến ở $8$ và $30$: các xóm $3, 8, 12, 13$ đi tới bến $8$, các xóm $27, 30, 34$ đi tới bến $30$. Tổng $1\cdot5 + 9\cdot0 + 3\cdot4 + 7\cdot5 + 4\cdot3 + 7\cdot0 + 4\cdot4 = 80$.

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 Hai bến đò

Lời mở đầu

Ta phải chọn cùng lúc hai vị trí $P, Q$ trong khoảng tới $10^9$ giá trị — không thể thử hết. Bài được "gỡ" nhờ hai nhận xét.

Nhận xét 1 – Chỉ có một bến thì đặt ở trung vị. Giả sử chỉ có một bến ở vị trí $P$ phục vụ một nhóm xóm. Nếu dời bến sang phải $1$ mét thì mọi người ở bên trái bến phải đi thêm $1$ mét, mọi người ở bên phải đi bớt $1$ mét. Vậy chừng nào số người bên phải còn nhiều hơn số người bên trái thì dời sang phải còn có lợi, và ngược lại. Bến tốt nhất nằm ở chỗ "cân": số người hai bên không bên nào vượt quá một nửa. Đó là trung vị có trọng số — khi xếp các xóm theo vị trí và cộng dồn số người từ trái sang, đó là xóm đầu tiên làm tổng cộng dồn đạt ít nhất một nửa tổng số người. Bến đặt ngay tại một xóm!

Nhận xét 2 – Hai bến chia các xóm thành "nửa trái" và "nửa phải". Giả sử $P \le Q$. Người đi tới bến gần hơn, nên mọi xóm bên trái điểm giữa $\frac{P+Q}{2}$ đi tới $P$, mọi xóm bên phải đi tới $Q$. Khi đã sắp xếp các xóm theo vị trí, nhóm đi tới $P$ luôn là một đoạn đầu và nhóm đi tới $Q$ là đoạn còn lại.

Hình 1. Sau khi sắp xếp, lời giải tối ưu luôn có dạng: cắt dãy xóm tại một chỗ $k$, mỗi nhóm dùng một bến đặt ở trung vị có trọng số của nhóm đó.

Như vậy chỉ còn $N + 1$ cách chia (kể cả chia "rỗng" – lúc đó hai bến trùng nhau). Ba cách làm dưới đây khác nhau ở chỗ ta thử và tính chi phí nhanh tới đâu.

Cách 1Thử mọi cặp bến · 20%Cách 2Thử mọi điểm chia · 50%Cách 3Tổng tiền tố + tìm nhị phân · 100%

Cách 1Thử mọi cặp vị trí bến – O(N³) · 20%

Theo Nhận xét 1, mỗi bến có thể đặt ngay tại vị trí một xóm nào đó. Vậy ta thử mọi cặp xóm $(p, q)$ làm hai bến, rồi duyệt qua mọi xóm tính tổng quãng đường (mỗi người chọn bến gần hơn). Có $N^2/2$ cặp, mỗi cặp tính trong $O(N)$: với $N = 100$ chỉ khoảng $5\cdot10^5$ phép tính.

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
int main() {
    int n;
    cin >> n;
    vector<ll> x(n), w(n);
    for (int i = 0; i < n; i++) cin >> x[i] >> w[i];
    ll ans = LLONG_MAX;
    // ben dat tai vi tri cac xom: thu moi cap (P, Q)
    for (int p = 0; p < n; p++)
        for (int q = p; q < n; q++) {
            ll tong = 0;
            for (int i = 0; i < n; i++)      // moi nguoi di toi ben gan hon
                tong += w[i] * min(llabs(x[i] - x[p]), llabs(x[i] - x[q]));
            ans = min(ans, tong);
        }
    cout << ans << '\n';
    return 0;
}

import sys

def main():
    data = sys.stdin.buffer.read().split()
    n = int(data[0])
    x = [int(v) for v in data[1:2 * n + 1:2]]
    w = [int(v) for v in data[2:2 * n + 2:2]]
    ans = None
    # ben dat tai vi tri cac xom: thu moi cap (P, Q)
    for p in range(n):
        P = x[p]
        for q in range(p, n):
            Q = x[q]
            tong = 0
            for i in range(n):               # moi nguoi di toi ben gan hon
                tong += w[i] * min(abs(x[i] - P), abs(x[i] - Q))
            if ans is None or tong < ans:
                ans = tong
    print(ans)

main()

Không gian$O(N)$

Thời gian$O(N^3)$

Cách này chưa cần sắp xếp

Cách 1 không cần biết xóm nào ở trái, xóm nào ở phải, nên dữ liệu không theo thứ tự cũng không sao. Nhưng từ Cách 2 trở đi, bước sắp xếp theo vị trí là bắt buộc.

Cách 2Thử mọi điểm chia – O(N²) · 50%

Sắp xếp các xóm theo vị trí. Theo Nhận xét 2, ta thử mọi điểm chia $k = 0, 1, \dots, N$: các xóm $0..k-1$ đi bến 1, các xóm $k..N-1$ đi bến 2. Với mỗi nhóm $l..r$:

1. Tính tổng số người $T$ của nhóm.
2. Đi từ $l$ sang phải, cộng dồn số người tới khi tổng cộng dồn $s$ thỏa $2s \ge T$: xóm đang đứng là trung vị $m$.
3. Chi phí của nhóm là $\sum_{i=l}^{r} w_i \cdot |x_i - x_m|$.

Mỗi nhóm tính trong $O(N)$, có $N + 1$ điểm chia nên tổng $O(N^2)$: với $N = 5000$ khoảng $5\cdot10^7$ phép tính, vẫn chạy kịp.

k	Nhóm trái	trung vị	chi phí trái	Nhóm phải	trung vị	chi phí phải	Tổng
0	(rỗng)	–	0	3..34	13	317	317
1	3	3	0	8..34	13	307	307
2	3, 8	8	5	12..34	27	192	197
3	3, 8, 12	8	17	13..34	27	147	164
4	3, 8, 12, 13	8	52	27, 30, 34	30	28	80
5	3..27	12	112	30, 34	30	16	128
6	3..30	13	233	34	34	0	233
7	3..34	13	317	(rỗng)	–	0	317

Bảng trên là chạy tay ví dụ của đề (các xóm ghi theo vị trí). Điểm chia tốt nhất là $k = 4$, cho đáp án $80$. Để ý trung vị của nhóm "$3, 8, 12, 13$" là $8$ chứ không phải xóm ở giữa theo thứ tự: xóm $8$ có tới $9$ người, một mình nó đã chiếm quá nửa nhóm ($9$ trên $20$ người, cộng xóm $3$ là $10 \ge 20/2$).

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
int n;
vector<ll> x, w;
// cac xom l..r (da sap xep) cung di toi 1 ben dat o trung vi co trong so
ll cost(int l, int r) {
    if (l > r) return 0;
    ll T = 0;
    for (int i = l; i <= r; i++) T += w[i];
    int m = l;
    ll s = w[l];
    while (2 * s < T) { m++; s += w[m]; }    // xom dau tien ma tong w tu l den m >= T/2
    ll tong = 0;
    for (int i = l; i <= r; i++) tong += w[i] * llabs(x[i] - x[m]);
    return tong;
}
int main() {
    cin >> n;
    vector<pair<ll, ll>> a(n);
    for (auto &p : a) cin >> p.first >> p.second;
    sort(a.begin(), a.end());                // sap xep theo vi tri
    x.resize(n); w.resize(n);
    for (int i = 0; i < n; i++) { x[i] = a[i].first; w[i] = a[i].second; }
    ll ans = LLONG_MAX;
    for (int k = 0; k <= n; k++)             // xom 0..k-1 -> ben 1, xom k..n-1 -> ben 2
        ans = min(ans, cost(0, k - 1) + cost(k, n - 1));
    cout << ans << '\n';
    return 0;
}

import sys

def cost(x, w, l, r):
    # cac xom l..r (da sap xep) cung di toi 1 ben dat o trung vi co trong so
    if l > r:
        return 0
    T = 0
    for i in range(l, r + 1):
        T += w[i]
    m = l
    s = w[l]
    while 2 * s < T:                         # xom dau tien ma tong w tu l den m >= T/2
        m += 1
        s += w[m]
    xm = x[m]
    tong = 0
    for i in range(l, r + 1):
        tong += w[i] * abs(x[i] - xm)
    return tong

def main():
    data = sys.stdin.buffer.read().split()
    n = int(data[0])
    a = sorted(zip(map(int, data[1:2 * n + 1:2]), map(int, data[2:2 * n + 2:2])))
    x = [p[0] for p in a]
    w = [p[1] for p in a]
    ans = None
    for k in range(n + 1):                   # xom 0..k-1 -> ben 1, xom k..n-1 -> ben 2
        c = cost(x, w, 0, k - 1) + cost(x, w, k, n - 1)
        if ans is None or c < ans:
            ans = c
    print(ans)

main()

Không gian$O(N)$

Thời gian$O(N^2)$

Cách 3Tổng tiền tố + tìm nhị phân trung vị – O(N log N) · 100%

Ở Cách 2, việc tốn thời gian là tính chi phí một nhóm $l..r$ trong $O(N)$. Ta làm nó trong $O(\log N)$ bằng hai mảng tổng tiền tố (các xóm đã sắp xếp):

$$SW[i] = w_0 + w_1 + \dots + w_{i-1}, \qquad SX[i] = w_0 x_0 + w_1 x_1 + \dots + w_{i-1} x_{i-1}.$$

• Tìm trung vị $m$: tổng số người $T = SW[r+1] - SW[l]$. Mảng $SW$ tăng dần, nên xóm đầu tiên có tổng cộng dồn (tính từ $l$) đạt $\lceil T/2 \rceil$ tìm được bằng lower_bound trên $SW$, giá trị cần tìm là $SW[l] + \lceil T/2 \rceil$.
• Tính chi phí: những người ở bên trái (và tại) $m$ đi quãng $x_m - x_i$, bên phải đi $x_i - x_m$. Tách tổng ra: $$\underbrace{x_m \cdot (SW[m+1]-SW[l]) - (SX[m+1]-SX[l])}_{\text{bên trái}} + \underbrace{(SX[r+1]-SX[m+1]) - x_m \cdot (SW[r+1]-SW[m+1])}_{\text{bên phải}}.$$

Ví dụ nhóm trái $3, 8, 12, 13$ của ví dụ ($l = 0, r = 3$): $SW = [0, 1, 10, 13, 20, \dots]$, $T = 20$, tìm giá trị $10$ trong $SW$ được vị trí $2$, nên $m = 1$ (xóm $x = 8$). Bên trái: $8 \cdot 10 - 75 = 5$; bên phải: $(202 - 75) - 8 \cdot 10 = 47$. Tổng $52$, khớp với bảng ở Cách 2.

Tràn số ở chỗ không ngờ

Tổng số người tới $2\cdot 10^9$, vị trí tới $10^9$ nên tích $x_m \cdot SW$ tới $2\cdot10^{18}$ — vừa đủ cho long long. Nếu lưu $x$ và $SW$ bằng int (vì "từng số đều vừa int") thì phép nhân x[m] * SW[...] được tính bằng int và tràn trước khi kịp gán vào biến long long. Lỗi này chỉ qua được 4/32 test.

Mô phỏng dưới đây sắp xếp các xóm, tính hai mảng tổng tiền tố rồi thử từng điểm chia $k$.

Vị trí x Số người w

Ví dụ nhanh:

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
int n;
vector<ll> x, SW, SX;   // SW[i] = tong w cua i xom dau; SX[i] = tong w*x cua i xom dau
// chi phi nho nhat khi cac xom l..r (da sap xep) cung di toi 1 ben
ll cost(int l, int r) {
    if (l > r) return 0;
    ll T = SW[r + 1] - SW[l];
    // trung vi co trong so: xom m dau tien ma tong w tu l den m >= nua T
    int m = lower_bound(SW.begin() + l + 1, SW.begin() + r + 2, SW[l] + (T + 1) / 2) - SW.begin() - 1;
    ll trai = x[m] * (SW[m + 1] - SW[l]) - (SX[m + 1] - SX[l]);
    ll phai = (SX[r + 1] - SX[m + 1]) - x[m] * (SW[r + 1] - SW[m + 1]);
    return trai + phai;
}
int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cin >> n;
    vector<pair<ll, ll>> a(n);               // (vi tri, so nguoi)
    for (auto &p : a) cin >> p.first >> p.second;
    sort(a.begin(), a.end());                // sap xep theo vi tri
    x.resize(n); SW.assign(n + 1, 0); SX.assign(n + 1, 0);
    for (int i = 0; i < n; i++) {
        x[i] = a[i].first;
        SW[i + 1] = SW[i] + a[i].second;
        SX[i + 1] = SX[i] + a[i].second * a[i].first;
    }
    ll ans = LLONG_MAX;
    for (int k = 0; k <= n; k++)             // xom 0..k-1 -> ben 1, xom k..n-1 -> ben 2
        ans = min(ans, cost(0, k - 1) + cost(k, n - 1));
    cout << ans << '\n';
    return 0;
}

import sys
from bisect import bisect_left

def main():
    data = sys.stdin.buffer.read().split()
    n = int(data[0])
    a = sorted(zip(map(int, data[1:2 * n + 1:2]), map(int, data[2:2 * n + 2:2])))
    x = [p[0] for p in a]
    SW = [0] * (n + 1)                       # SW[i] = tong w cua i xom dau
    SX = [0] * (n + 1)                       # SX[i] = tong w*x cua i xom dau
    for i in range(n):
        xi, wi = a[i]
        SW[i + 1] = SW[i] + wi
        SX[i + 1] = SX[i] + wi * xi

    def cost(l, r):
        # chi phi nho nhat khi cac xom l..r cung di toi 1 ben
        if l > r:
            return 0
        T = SW[r + 1] - SW[l]
        m = bisect_left(SW, SW[l] + (T + 1) // 2, l + 1, r + 2) - 1
        xm = x[m]
        trai = xm * (SW[m + 1] - SW[l]) - (SX[m + 1] - SX[l])
        phai = (SX[r + 1] - SX[m + 1]) - xm * (SW[r + 1] - SW[m + 1])
        return trai + phai

    ans = cost(0, n - 1)
    for k in range(1, n):                    # xom 0..k-1 -> ben 1, xom k..n-1 -> ben 2
        c = cost(0, k - 1) + cost(k, n - 1)
        if c < ans:
            ans = c
    print(ans)

main()

Không gian$O(N)$

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

C++▶ Chạy tay từng dòng codeSắp xếp, tính SW và SX, rồi thử mọi điểm chia k; mỗi nhóm tìm trung vị bằng lower_bound.

Dữ liệu vào (stdin) – sửa thoải mái7 3 1 8 9 12 3 13 7 27 4 30 7 34 4

Dữ liệu mẫu:

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

2using namespace std;

3typedef long long ll;

4int n;

5vector<ll> x, SW, SX; // SW[i] = tong w cua i xom dau; SX[i] = tong w*x cua i xom dau

6// chi phi nho nhat khi cac xom l..r (da sap xep) cung di toi 1 ben

7ll cost(int l, int r) {

8 if (l > r) return 0;

9 ll T = SW[r + 1] - SW[l];

10 // trung vi co trong so: xom m dau tien ma tong w tu l den m >= nua T

11 int m = lower_bound(SW.begin() + l + 1, SW.begin() + r + 2, SW[l] + (T + 1) / 2) - SW.begin() - 1;

12 ll trai = x[m] * (SW[m + 1] - SW[l]) - (SX[m + 1] - SX[l]);

13 ll phai = (SX[r + 1] - SX[m + 1]) - x[m] * (SW[r + 1] - SW[m + 1]);

14 return trai + phai;

15}

16int main() {

17 ios::sync_with_stdio(false);

18 cin.tie(nullptr);

19 cin >> n;

20 vector<pair<ll, ll>> a(n); // (vi tri, so nguoi)

21 for (auto &p : a) cin >> p.first >> p.second;

22 sort(a.begin(), a.end()); // sap xep theo vi tri

23 x.resize(n); SW.assign(n + 1, 0); SX.assign(n + 1, 0);

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

25 x[i] = a[i].first;

26 SW[i + 1] = SW[i] + a[i].second;

27 SX[i + 1] = SX[i] + a[i].second * a[i].first;

28 }

29 ll ans = LLONG_MAX;

30 for (int k = 0; k <= n; k++) // xom 0..k-1 -> ben 1, xom k..n-1 -> ben 2

31 ans = min(ans, cost(0, k - 1) + cost(k, n - 1));

32 cout << ans << '\n';

33 return 0;

34}

ChậmVừaNhanhRất nhanh

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

Bộ test có 32 test: Subtask 1 có 10 test ($N \le 100$; gồm ví dụ, $N = 1$, $N = 2$, ba xóm cùng một chỗ), Subtask 2 có 10 test ($N \approx 5000$), Subtask 3 có 12 test ($N \approx 2\cdot 10^5$). Dữ liệu luôn bị xáo trộn thứ tự; các kiểu: ngẫu nhiên, vài xóm cực đông giữa nhiều xóm vắng, 3–4 cụm xóm (khe lớn nhất không phải chỗ chia đúng), cách đều, nhiều xóm trùng vị trí, toàn xóm $10^4$ người (đáp án tới $1{,}6\cdot10^{17}$). Điểm tính theo từng test (thang 100%).

Cách làm	Sub 1 (10 test)	Sub 2 (10 test)	Sub 3 (12 test)	Điểm
Cách 1 – Thử mọi cặp bến, $O(N^3)$	Đúng 10/10	TLE 0/10	TLE 0/12	20
Cách 2 – Thử mọi điểm chia, $O(N^2)$	Đúng 10/10	Đúng 10/10	TLE 0/12	50
Cách 3 – Tổng tiền tố + tìm nhị phân (chuẩn)	Đúng 10/10	Đúng 10/10	Đúng 12/12	100
Sai: trung vị theo số xóm (bỏ qua số người)	WA 6/10	WA 1/10	WA 2/12	23,3
Sai: chia nhóm ở khe lớn nhất giữa hai xóm	WA 6/10	WA 1/10	WA 2/12	23,3
Sai: chia hai nhóm có số người bằng nhau	WA 4/10	WA 0/10	WA 0/12	8
Sai: lưu $x$, $SW$ bằng int (tích tràn)	WA 4/10	WA 0/10	WA 0/12	8
Sai: quên sắp xếp	WA 3/10	WA 0/10	WA 0/12	6

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à quá thời gian (hơn 3 giây) ở toàn bộ 22 test còn lại; Cách 2 đúng 20/20 test của hai subtask đầu và quá thời gian ở cả 12 test Subtask 3; Cách 3 đúng 32/32 test, test lâu nhất chạy khoảng 0,1 giây. Lời giải Python của Cách 3 cũng đúng 32/32 test, chạy tối đa khoảng 3,5 giây với CPython (PyPy nhanh hơn nhiều). Ví dụ của đề đã xếp sẵn theo vị trí và khá "hiền": cả năm lời giải sai trong bảng đều ra đúng $80$ — nên nhớ kiểm tra thêm bằng test tự nghĩ 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 😇