Buôn thực phẩm

Nguồn: CLUE OJ – Chương 14: Cửa sổ trượt + Tham lam Độ khó: Trung bình Tham lam Sắp xếp

Đề bài

Tèo cần mua $K$ đơn vị thực phẩm trên đường đi tới thành phố. Việc lái xe $D$ km với $K$ đơn vị thực phẩm trên xe sẽ tiêu tốn $D \times K$ xu.

Thức ăn được bán tại $N$ cửa hàng, mỗi cửa hàng nằm trên một đoạn của trục số $X$.

Cửa hàng thứ $i$ nằm tại toạ độ $X_i$ trên trục số.
Mỗi cửa hàng có thể bán tối đa $F_i$ đơn vị thức ăn với giá $C_i$ xu mỗi đơn vị.

Tèo xuất phát từ vị trí 0 và chỉ có thể di chuyển theo hướng dương đến vị trí $E$, với điều kiện phải mang được ít nhất $K$ đơn vị thức ăn khi đến nơi. Anh ta có thể dừng lại tại bất kỳ cửa hàng nào trên đường và mua bất kỳ số lượng thức ăn nào, miễn là không vượt quá số lượng tối đa mà cửa hàng có thể bán.

Hãy tính số tiền tối thiểu Tèo cần trả để mua và vận chuyển $K$ đơn vị thức ăn từ 0 đến $E$. Dữ liệu đảm bảo rằng luôn tồn tại một giải pháp.

Dữ liệu:

Dòng đầu tiên chứa ba số nguyên $K$, $E$ và $N$ $(1 \le K \le 10^6,\ 1 \le E \le 10^8,\ 1 \le N \le 10^6)$.
$N$ dòng tiếp theo, mỗi dòng chứa ba số nguyên $X_i, F_i, C_i$ $(0 < X_i \le E,\ 1 \le F_i \le 10^6,\ 1 \le C_i \le 10^6)$.

Kết quả: một số nguyên duy nhất là chi phí tối thiểu để Tèo mua đủ $K$ đơn vị thức ăn và đến vị trí $E$.

Ràng buộc: 50% số test đầu tiên có $1 \le K \le 100$, $1 \le E \le 350$, $1 \le N \le 100$, $0 < X_i \le E$, $1 \le F_i \le 100$, $1 \le C_i \le 1\,000\,000$. 50% số test còn lại không có giới hạn gì thêm.

Giải thích ví dụ: Tèo cần mua 2 đơn vị thức ăn để di chuyển từ vị trí 0 đến 5. Một giải pháp tối ưu là:

Dừng tại cửa hàng thứ hai $(X = 3)$, mua 1 đơn vị thức ăn với giá 2 xu.
Dừng tại cửa hàng thứ ba $(X = 4)$, mua 1 đơn vị thức ăn với giá 2 xu.
Chi phí vận chuyển: từ 3 đến 4 với 1 đơn vị thức ăn: $1 \times 1 = 1$ xu; từ 4 đến 5 với 2 đơn vị thức ăn: $1 \times 2 = 2$ xu.
Tổng chi phí: $4 + 1 + 2 = 7$ xu.

(Lưu ý nhỏ của mình: "cửa hàng thứ hai/thứ ba" ở đây là thứ tự theo toạ độ tăng dần $1, 3, 4$; theo thứ tự trong input thì đó là cửa hàng 1 $(X = 3)$ và cửa hàng 2 $(X = 4)$.)

Ví dụ – input

Ví dụ – output

Lời mở đầu

Bài này là bản dịch của bài Buying Feed (USACO). Thoạt nhìn ta nghĩ phải mô phỏng chiếc xe đi dọc trục số, lúc nào mua, mua bao nhiêu... và cách tự nhiên là quy hoạch động. Nhưng chỉ cần nhìn chi phí theo từng đơn vị thức ăn thì bài trở thành một bài tham lam sắp xếp rất ngắn. Mình trình bày cả hai.

Dành cho học viên · Ưu tiênNộp bài trên hệ thống CLUE OJ

Link này chỉ học viên đã tham gia tổ chức mới vào được. Học viên nên ưu tiên nộp ở đây vì sẽ được chấm nhanh hơn.

Nộp bài trên CLUE OJ

Lộ trình lời giải, bấm vào từng phần để nhảy tới:

Bộ test100 test Ý tưởnggiá trọn gói Cách 1QHĐ Cách 2tham lam

Bộ testBộ test chính thức có gì?

Bộ test có 100 test:

Test	N	K lớn nhất	E lớn nhất	$F_i$ lớn nhất	$C_i$ lớn nhất	Đáp án
1–20	2 … 5	19	20	10	10	4 … 257
21–50	100	97	98	997.568	998.403	102 … 2.848
51–60	1.000	732.985	81.692.426	999.958	999.024	126.213.528 … 4.913.919.527.920
61–70	10.000	715.730	62.013.049	999.977	999.849	3.214.020 … 83.228.705.753
71–90	100.000	944.105	93.458.767	999.998	999.999	10.019 … 15.539.839.682
91–100	1.000.000	935.300	97.248.821	999.998	999.999	81.708 … 2.996.074.864

Test 1–50 đúng là subtask 1 về $K, E, N$. Tuy nhiên test 21–50 có $F_i$ lên tới gần $10^6$, vượt giới hạn $F_i \le 100$ mà đề ghi cho subtask này – không sao, code QHĐ ở dưới chỉ mua tối đa $K - j$ đơn vị nên vẫn chạy nhanh.
Các cửa hàng không được cho theo thứ tự toạ độ $X$ – nếu làm QHĐ phải sắp xếp trước. Có thể có nhiều cửa hàng cùng toạ độ.
Ví dụ của đề không nằm trong bộ test (test 1 là một test nhỏ khác).

Subtask	Đề ghi	Test thật	Cách 1 QHĐ	Cách 2 tham lam
50% đầu	$K \le 100,$ $E$ $\le 350,$ $N$ $\le 100,$ $F_i$ $\le 100$	1–50	50/50	50/50
50% còn lại	$K, N \le 10^6,\ E \le 10^8$	51–100	0/50	50/50

Nhớ dùng long long

Một đơn vị có thể tốn tới $C + E \approx 10^6 + 10^8$ xu, nhân với $K = 10^6$ đơn vị là cỡ $10^{14}$. Đáp án lớn nhất trong bộ test là 4.913.919.527.920 – phải dùng long long, và nhân b * u[i].first cũng phải là long long.

Ý tưởngMỗi đơn vị thức ăn có một "giá trọn gói"

Chi phí lái xe là (quãng đường) × (số đơn vị trên xe). Ta có thể "chia" chi phí này cho từng đơn vị: một đơn vị mua ở toạ độ $X$ thì nằm trên xe đúng từ $X$ đến $E$, nên nó "gánh" đúng $E - X$ xu tiền chở. Tổng chi phí chở của cả xe bằng tổng các khoản này.

Nhận xét then chốt

Một đơn vị mua ở cửa hàng $i$ tốn tổng cộng $C_i + (E - X_i)$ xu, không phụ thuộc các đơn vị khác được mua ở đâu.

Kiểm tra với ví dụ: cửa hàng $X = 3$: $2 + 2 = 4$; cửa hàng $X = 4$: $2 + 1 = 3$; cửa hàng $X = 1$: $1 + 4 = 5$. Mua 1 đơn vị giá 3 và 1 đơn vị giá 4 → $7$. Đúng đáp án!

Vì các đơn vị độc lập, bài toán thành: có $N$ "quầy", quầy $i$ bán tối đa $F_i$ đơn vị với giá $C_i + E - X_i$; mua đủ $K$ đơn vị rẻ nhất. Hiển nhiên tham lam mua ở quầy rẻ nhất trước, hết hàng thì sang quầy rẻ tiếp theo (nếu có một đơn vị mua ở quầy đắt trong khi quầy rẻ hơn còn hàng, đổi sang quầy rẻ sẽ không tệ hơn).

Em nhập $K$, $E$ và các cửa hàng (bộ X F C, cách nhau dấu phẩy) rồi bấm Tiếp:

K = E = Cửa hàng (X F C):

Ví dụ nhanh:

Cách 1Quy hoạch động – 50% điểm

Cách "chưa nghĩ ra mẹo": sắp các cửa hàng theo $X$, đi dần từ trái sang phải. Gọi dp[j] = chi phí ít nhất để tới vị trí hiện tại mà trên xe có đúng $j$ đơn vị ($0 \le j \le K$).

Đi thêm $d$ km: dp[j] += d * j.
Tại cửa hàng $i$, mua thêm $b$ đơn vị ($0 \le b \le F_i$, $j + b \le K$): nd[j + b] = min(nd[j + b], dp[j] + b * C[i]).
Cuối cùng chở $K$ đơn vị từ cửa hàng cuối tới $E$.

C++▶ Chạy tay từng dòng codeCách 1: QHĐ dp[j] = chi phí ít nhất khi đang chở j đơn vị, đi qua từng cửa hàng theo X.

Dữ liệu vào (stdin) – sửa thoải mái

Dữ liệu mẫu:

Không gian$O(N + K)$

Thời gian$O(N \log N + N \cdot K \cdot \min(F, K))$

Kết quả chạy thật: bản C++ đúng 50/100 test (sai/quá thời gian ở test 51–100), test đúng chạy lâu nhất 0.01s. Bản Python: bản Python đúng 50/100 test (sai/quá thời gian ở test 51–100), test đúng chạy lâu nhất 0.07s. Ăn trọn 50% đầu. Ở nửa sau, mảng dp mình chỉ khai báo cho $K \le 100$ nên chạy sai; mà kể cả khai báo đủ $10^6$ phần tử thì số phép tính $N \cdot K \cdot \min(F, K)$ cũng lên tới hàng nghìn tỉ – không thể kịp.

Cách 2Tham lam theo giá trọn gói – Full điểm

C++▶ Chạy tay từng dòng codeCách 2: giá trọn gói C + (E − X), mua rẻ nhất trước.

Dữ liệu vào (stdin) – sửa thoải mái

Dữ liệu mẫu:

Lưu mỗi cửa hàng thành cặp (giá trọn gói, F); sort cặp sẽ xếp theo giá tăng dần.
Không cần sắp theo $X$, cũng không cần mô phỏng chiếc xe – toạ độ đã "nằm" trong giá trọn gói.
Vòng lặp dừng ngay khi need == 0.

Không gian$O(N)$

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

Kết quả chạy thật: bản C++ đúng 100/100 test, test đúng chạy lâu nhất 0.39s. Bản Python: bản Python đúng 90/100 test (sai/quá thời gian ở test 91–100), test đúng chạy lâu nhất 0.20s. Bản Python đã dùng mẹo gói (giá, F) vào một số nguyên để sắp xếp nhanh hơn, nhưng với $N = 10^6$ (phải đọc $3 \cdot 10^6$ số) vẫn mất khoảng 2 giây nên quá thời gian ở 10 test cuối – thuật toán đúng, chỉ là Python chậm. Nộp bài thì các bạn dùng bản C++ nhé.

Tổng kếtKết quả chạy thật trên bộ test

Cách	Ngôn ngữ	Đúng	Test đúng lâu nhất	Ghi chú
1. Quy hoạch động theo số đơn vị đang chở	C++	50/100	0.01s	Qua 50% đầu
	Python	50/100	0.07s
2. Tham lam theo giá trọn gói	C++	100/100	0.39s	Full điểm
	Python	90/100	0.20s	Quá thời gian test 91–100

Ghi chú của mình: thời gian trong bảng là thời gian CPU đo trên máy của mình (giới hạn 1 giây). Mẹo "phân bổ chi phí chung về từng đơn vị" biến một bài tưởng phải QHĐ thành tham lam một dòng sắp xếp. Nếu muốn nhanh hơn nữa có thể thay sort bằng nth_element hoặc đếm phân phối, nhưng ở đây sort đã đủ.

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 😇

Lập Trình Thuật Toán