Tuyến xe điện

Nguồn: CLUE OJ Độ khó: Dễ Mảng 1 chiều Mô phỏng

Đề bài

Tỉnh quyết định đầu tư tuyến xe điện từ biển Triệu Lăng lên Đông Hà. Tuyến có $n$ điểm dừng, được đánh số từ $1$ đến $n$ theo thứ tự xe chạy. Theo khảo sát, tại điểm dừng thứ $i$ sẽ có $a_i$ khách xuống xe và $b_i$ khách lên xe. Xe trống khi tới điểm dừng đầu tiên, và tới điểm dừng cuối cùng thì toàn bộ hành khách xuống hết để xe trống trở lại.

Tại mỗi điểm dừng, tất cả khách xuống xe trước, sau đó khách mới lên. Hãy tính số ghế ít nhất của xe để lúc nào mỗi hành khách cũng có một ghế riêng.

Dữ liệu vào:

• Dòng đầu tiên là số nguyên $n$ – số điểm dừng.
• $n$ dòng tiếp theo, dòng thứ $i$ gồm hai số nguyên $a_i$ và $b_i$ lần lượt là số khách xuống và số khách lên tại điểm dừng $i$.

Kết quả:

In ra số ghế ít nhất cần có.

Giới hạn:

• $2 \le n \le 999$
• $0 \le a_i, b_i \le 10^6$
• Dữ liệu đảm bảo: $a_1 = 0$; số khách xuống ở mỗi điểm dừng không vượt quá số khách đang có trên xe; ở điểm dừng cuối $b_n = 0$ và $a_n$ bằng đúng số khách còn trên xe.

Giới hạn thời gian: 1 giây, bộ nhớ: 256 MB. Dữ liệu nhập từ bàn phím và in ra màn hình.

Ví dụ 1 – input

4
0 3
2 5
4 2
4 0

Ví dụ 1 – output

6

• Điểm 1: 0 khách xuống, 3 khách lên → trên xe có 3 người.
• Điểm 2: 2 khách xuống (còn 1), 5 khách lên → 6 người.
• Điểm 3: 4 khách xuống (còn 2), 2 khách lên → 4 người.
• Điểm 4: 4 khách xuống hết.

Lúc đông nhất có 6 người nên xe cần ít nhất 6 ghế.

Nguồn: phỏng theo bài "XE BUÝT" – vinhdinhcoder.net (chủ đề Mảng 1 chiều).

Lời mở đầu

Mô phỏng chiếc xe chạy qua từng trạm: trừ khách xuống, cộng khách lên, và ghi nhớ lúc xe đông nhất. Ghi chú: đề gốc mâu thuẫn – phần mô tả nói "$a_i$ khách xuống, $b_i$ khách lên" nhưng phần dữ liệu vào lại viết "$a_i, b_i$ là số khách lên và xuống"; ví dụ chỉ khớp với cách hiểu $a_i$ = xuống, $b_i$ = lên nên mình chốt như vậy. Ràng buộc gốc "$|A_i| < 10^6$" không rõ nghĩa, mình sửa thành $2 \le n \le 999$, $0 \le a_i, b_i \le 10^6$ và dữ liệu luôn hợp lệ.

Link nộp bài

Bấm vào nút bên dưới để nộp bài và được hệ thống CLUE OJ chấm tự động.

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ộ test20 testÝ tưởngmô phỏng + maxLời giảicode C++ / PythonCái bẫycách làm saiTổng kếtkết quả

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

Bộ test có 20 test, mỗi test đúng được 1 phần điểm như nhau. Mọi test có $n \le 999$, dữ liệu hợp lệ (không ai xuống khi xe trống, cuối tuyến xuống hết).

Test	Nội dung kiểm tra
1	Ví dụ của đề
2	Không có hành khách nào: đáp án 0
3–6	Tuyến ngắn, lúc đông nhất ở trạm đầu / giữa
7–11	Ngẫu nhiên, 10 – 200 trạm
12–20	777 – 999 trạm; có test khách chỉ lên mà không xuống (đáp án gần $10^6$)

Ý tưởngĐi theo xe, trạm nào cũng cập nhật max

Gọi trenXe là số khách đang ngồi trên xe. Tại trạm $i$: trenXe -= a[i] rồi trenXe += b[i]. Ngay sau khi khách lên là lúc xe đông nhất của trạm đó, nên ta so với soGhe và giữ lại giá trị lớn nhất.

Đọc kỹ thứ tự trong dữ liệu

Mỗi dòng là "xuống trước, lên sau". Hiểu ngược ($a$ là lên, $b$ là xuống) cho kết quả sai hoàn toàn. Ví dụ của đề giúp em kiểm tra: $0\ 3$ ở trạm đầu – xe đang trống nên chắc chắn 0 là số khách xuống.

Em nhập các trạm theo dạng xuống lên (mỗi trạm cách nhau dấu phẩy) rồi bấm Tiếp:

s =

Ví dụ nhanh:

Lời giảiMô phỏng từng trạm

Lưu số khách xuống/lên vào hai mảng a, b, rồi đi qua từng trạm.

C++▶ Chạy tay từng dòng codeTrừ khách xuống, cộng khách lên, cập nhật soGhe.

Dữ liệu vào (stdin) – sửa thoải mái4 0 3 2 5 4 2 4 0

Dữ liệu mẫu:

ChậmVừaNhanhRất nhanh

1. Chỉ cần so sánh sau khi khách lên: lúc vừa xuống xong luôn ít người hơn.
2. Số khách trên xe tối đa khoảng $10^9$ – vừa đủ trong int, nhưng dùng long long cho chắc.

Không gian$O(n)$

Thời gian$O(n)$

Kết quả chạy thật: bản C++ đúng 20/20 test, chạy lâu nhất 0.003s. Bản Python đúng 20/20 test, chạy lâu nhất 0.022s. Full điểm.

Cái bẫyNhững cách làm sai hay gặp

Các cách làm sai mình đã chấm thử trên bộ test:

Cách làm sai	Đúng	Ghi chú
Hiểu ngược: $a_i$ là số khách lên, $b_i$ là số khách xuống	1/20	sai test 1, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20
Quên trừ khách xuống (cộng dồn số khách lên)	3/20	sai test 1, 4, 5, 6, 7, 8, 9, 10, 11, 12, 14, 15, 16, 17, 18, 19, 20
Lấy số khách lên nhiều nhất ở một trạm	4/20	sai test 1, 5, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20

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

Cách	Ngôn ngữ	Đúng	Lâu nhất	Ghi chú
Lời giải chuẩn	C++	20/20	0.003s	Full điểm
	Python	20/20	0.022s	Full điểm
Hiểu ngược a, b	C++	1/20	–	Mất 19 test
Quên trừ	C++	3/20	–	Mất 17 test
Max lượt lên	C++	4/20	–	Mất 16 test

Ghi chú của mình: khi đề viết lộn xộn, ví dụ là trọng tài: thử cả hai cách hiểu trên ví dụ, cách nào ra đúng kết quả thì theo cách đó.

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 😇