Thang máy
Đề bài
Có $n$ người đang đứng chờ trước một thang máy duy nhất tại tầng trệt trong một tòa cao ốc cao 2000 tầng, họ muốn đi đến các tầng trong tòa nhà. Các tầng của cao ốc được đánh số $1, 2, 3, 4, \ldots, 2000$. Tầng trệt là tầng 1. Người thứ $i$ muốn đi đến tầng $a_i$. Thang máy chỉ chở được $k$ người cùng lúc.
Thời gian thang máy đi từ tầng $x$ đến tầng $y$ là $|x - y|$ giây. Hãy tính thời gian tối thiểu để thang máy có thể vận chuyển hết $n$ người đến tầng mà họ mong muốn và thang máy quay trở lại tầng trệt. (giả sử thời gian ra vào thang máy là không đáng kể)
Dữ liệu nhập: gồm 2 dòng
- Dòng thứ nhất là 2 số nguyên $n, k$ cách nhau một khoảng trắng ($1 \le n, k \le 2000$)
- Dòng thứ hai gồm $n$ số nguyên $a_i$, mỗi số cách nhau một khoảng trắng ($2 \le a_i \le 2000$)
Dữ liệu xuất:
- Là một số nguyên xác định thời gian tối thiểu để đạt được mục đích.
3 2
2 3 484 2
50 100 50 10029610 3
2 2 2 2 2 2 2 2 2 28Giải thích ví dụ 1:
- Lần thứ nhất chở 2 người lên tầng 3, 4 và quay lại trệt: 6 giây.
- Lần thứ hai chở 1 người lên tầng 2 và quay lại trệt: 2 giây.
Lời mở đầu
Bài này mình được một bạn học viên hỏi nên sẵn tiện mình viết bài giải chi tiết để nhiều bạn được tham khảo luôn. Hy vọng mang đến được giá trị cho các bạn 😇.
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 OJBạ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é. Chưa có tài khoản thì tạo tài khoản rồi đăng nhập nộp bài thử hen.
Nộp bài trên CodeforcesHiểu đề: trị tuyệt đối $|x - y|$
Trong đề có đoạn: Thời gian thang máy đi từ tầng $x$ đến tầng $y$ là $|x - y|$ giây. Cái $|\;|$ ở đây là ký hiệu của trị tuyệt đối trong toán học các bạn nhé. Bạn nào không nhớ thì mình nhắc lại:
Tóm lại trị tuyệt đối giúp biến kết quả bên trong nó: số dương thì vẫn giữ nguyên, còn số âm thì biến thành giá trị dương tương ứng (biến dấu − thành dấu +). Vậy với $x$ là tầng hiện tại, $y$ là tầng đích đến, $|x - y|$ nghĩa là cứ lấy 2 tầng trừ nhau, kết quả âm thì biến thành dương, hay có thể hiểu là cứ lấy tầng lớn trừ tầng nhỏ.
Nhận diện phương pháp: tham lam
Bài này dùng phương pháp tham lam để xử lý thôi. Kể cả bạn nào không biết về phương pháp tham lam thì thực ra đôi khi các bạn đang giải quyết vấn đề theo chính tư tưởng của tham lam mà các bạn không biết.
Tại sao bài này lại nhìn ra được tư tưởng tham lam? Đọc đề là thấy rõ mùi rồi hehe: xử lý theo quy luật gì đó để sau cùng đáp án phải là nhỏ nhất / lớn nhất, đọc kiểu này phát thấy mùi tham lam ngay. Tham lam chỉ là dạng tư tưởng thôi, còn để hiện thực được nó thì có thể cần đến những kỹ thuật bổ trợ khác nữa, như ngay trong chính bài này, các bạn cứ tiếp tục xem nhé.
Quan sát mấu chốt
Cái đánh lừa của bài này ở câu: Thời gian đi từ tầng $x$ đến tầng $y$ là $|x - y|$ giây, làm ta có cảm giác phải đi tính thời gian cụ thể trong mỗi lần di chuyển giữa mỗi tầng. Nhưng nhìn kỹ hơn thì ta sẽ thấy như sau (trục ngang là chiều của tòa nhà từ dưới lên trên):
Giả sử cần chở một nhóm người lên đủ các tầng 2, 3, 4: từ tầng 1 đến tầng 2 mất $|1 - 2| = 1$ giây, từ tầng 2 đến tầng 3 mất $|2 - 3| = 1$ giây, từ tầng 3 đến tầng 4 mất $|3 - 4| = 1$ giây, rồi từ tầng 4 xuống tầng 1 mất $|4 - 1| = 3$ giây. Tổng cộng: $1 + 1 + 1 + 3 = 6$ giây.
Nhìn trên hình các bạn sẽ thấy rõ: đoạn $1 \to 4$ (màu cam) bao chứa hoàn toàn 3 đoạn $1 \to 2$, $2 \to 3$, $3 \to 4$ ở trên. Vậy khi trong nhóm có người cần đến tầng 4 (tầng cao nhất trong nhóm) thì ta cứ tính thẳng:
Chiến lược tham lam
Vậy thời gian lâu nhất đến từ việc phải đi lên tầng càng cao. Giải pháp tham lam ở đây là: nếu có người cần lên những tầng cao thì hãy cố gom càng nhiều người lên những tầng cao đó vào cùng một lần đi, để các lần sau ít phải đi lên cao như vậy, chứ không thì lần nào cũng có người cần lên tầng cao, lại tốn rất nhiều thời gian.
Ví dụ: có 3 người cần lên các tầng 2, 3, 4, thang máy mỗi lần chở tối đa 2 người.
Kiểm tra với các ví dụ mẫu
| Ví dụ | Các lần chở (tầng cao nhất được tô cam) | Tổng |
|---|---|---|
| 1: tầng 2, 3, 4; $k = 2$ | 3 4 → $3 \times 2 = 6$ 2 → $1 \times 2 = 2$ | 8 |
| 2: tầng 50, 100, 50, 100; $k = 2$ | 100 100 → $99 \times 2 = 198$ 50 50 → $49 \times 2 = 98$ | 296 |
| 3: mười người đều lên tầng 2; $k = 3$ | 4 lần chở lên tầng 2 → $|1 - 2| \times 2 \times 4$ | 8 |
Em nhập $k$ và danh sách tầng của từng người, rồi bấm Tiếp để xem thang máy chở từng nhóm theo chiến lược tham lam:
Cài đặt: sắp xếp giảm dần rồi nhảy từng bước $k$
Ta sắp xếp danh sách các tầng của $N$ người theo thứ tự giảm dần, tức là tầng cao nhất nằm ở đầu. Rồi xét từng đoạn $K$ phần tử từ đầu đến cuối, mỗi đoạn chọn phần tử đầu tiên, chính là tầng cao nhất trong $K$ người đó, để tính thời gian.
Ví dụ danh sách 10 tầng (index 0 đến 9), $K = 3$:
Danh sách 5 tầng, $K = 2$:
Danh sách 3 tầng, $K = 5$ (mọi người đi chung 1 lần):
Ô màu cam là index dùng để tính thời gian: $0, 0 + K, 0 + 2K, \ldots$
Các bạn có nhìn ra quy luật không? Index tính từ 0 và cứ thế bước nhảy $+K$: với $K = 3$ là $0, 3, 6, 9$; với $K = 2$ là $0, 2, 4$; với $K = 5$ chỉ có $0$. Đến đây các bạn đã thấy rõ quy luật xử lý rồi hen.
Source code
Source code để các bạn tham khảo với tư tưởng xử lý ở trên:
#include <bits/stdc++.h>
using namespace std;
int main(){
ios::sync_with_stdio(0);
cin.tie(0);
int n, k;
cin >> n >> k;
int a[n];
for(int i = 0; i < n; ++i){
cin >> a[i];
}
sort(a, a + n, greater<int>());
long long res = 0;
for(int i = 0; i < n; i += k){
res += (a[i] - 1) * 2;
}
cout << res;
return 0;
}import sys
data = sys.stdin.read().strip().split()
it = iter(data)
n = int(next(it))
k = int(next(it))
a = [int(next(it)) for _ in range(n)]
a.sort(reverse=True)
res = 0
for i in range(0, n, k):
res += (a[i] - 1) * 2
print(res)Giải thích code
1. Hai dòng đầu hàm main
ios::sync_with_stdio(0); cin.tie(0); giúp tăng tốc nhập xuất của C++. Mặc định cin/cout được đồng bộ với scanf/printf của C nên chạy khá chậm. Dòng thứ nhất tắt sự đồng bộ này, dòng thứ hai bỏ việc tự động xả bộ đệm cout mỗi lần cin đọc dữ liệu, nhờ vậy tốc độ nhập xuất của cin/cout nhanh ngang ngửa C. Trong các bài cần nhập xuất nhiều, như bài này $N$ tối đa là 2000 số, ta nên thêm 2 dòng này vào đầu cho chương trình chạy nhanh hơn. Lưu ý sau khi thêm thì đừng dùng lẫn scanf/printf với cin/cout trong cùng chương trình nhé. Code các bài lập trình thi đấu ta thường dùng C++ vì cú pháp ngắn gọn và nhiều hỗ trợ, nên bạn nào code C++ thì nhớ thêm 2 dòng này vào đầu hàm main.
2. Hàm sort
sort(a, a + n, greater<int>()); là hàm sắp xếp có sẵn trong thư viện giải thuật của C++ với độ phức tạp $O(N \log N)$. Ý nghĩa: sắp xếp danh sách bắt đầu từ phần tử đầu tiên (a), đủ n phần tử (a + n), theo tiêu chí giảm dần (greater<int>()). Nếu bỏ tham số thứ 3, chỉ còn sort(a, a + n); thì sắp xếp theo tiêu chí tăng dần. Bên Python, a.sort(reverse=True) cũng là sắp xếp giảm dần.
3. Vòng lặp tính tổng thời gian
Sau khi sắp giảm dần, đầu danh sách là những phần tử lớn nhất. Ta duyệt từ đầu về cuối với bước lặp i += k, với mỗi index i hợp lệ thì tính thời gian đi từ tầng 1 đến tầng a[i], vì đó là tầng cao nhất trong nhóm $k$ tầng cần đi. Tính cả chiều đi và về nên công thức là $|1 - a_i| \times 2$. Do tầng 1 là tầng thấp nhất nên không cần gọi abs(1 - a[i]), cứ lấy a[i] - 1 vì bảo đảm luôn ra số dương, rồi nhân 2 và cộng dồn vào biến res. Kết thúc vòng lặp thì in ra res, chính là tổng thời gian ít nhất.
Độ phức tạp
- Không gian: $O(N)$ với $N$ là số phần tử của mảng.
- Thời gian: $O(N)$ cho bước nhập mảng + $O(N \log N)$ cho bước sắp xếp giảm dần + $O(N / K)$ cho bước duyệt tính tổng. Theo quy tắc cộng Big O, lấy thành phần lớn nhất nên độ phức tạp là $O(N \log N)$.
Trường hợp xấu nhất $N = 2000$, $K = 1$: số lần lặp khoảng $2000 + 2000 \times \log_2 2000 + 2000$ $\approx 2000 + 2000 \times 11 + 2000$ $= 26\,000$ lần. Với giới hạn 1 giây, ngưỡng số lần lặp an toàn khoảng $(3 \text{ đến } 5) \times 10^7$, cao lắm là $10^8$, nên $26\,000 \approx 3 \times 10^4$ ít hơn ngưỡng cả nghìn lần, yên tâm không sợ bị TLE.
sort mà dùng các thuật toán sắp xếp $O(N^2)$ như Interchange Sort, Bubble Sort, Selection Sort… thì cũng không sợ TLE vì $2000^2 = 4 \times 10^6$ vẫn chưa vượt ngưỡng. Nhưng nếu đề nâng giới hạn $N$ lên 20 000 chẳng hạn thì sắp xếp $O(N^2)$ chắc chắn bị TLE. Mình khuyên các bạn cứ dùng hàm sort luôn vì nó đảm bảo $O(N \log N)$, có thể xem là tốt nhất khi dữ liệu lộn xộn không quy tắc, mà lại nhanh gọn để gọi ra hehe. Bạn nào chưa biết thì nên tìm hiểu về hàm này đi nhé.
Nhận xét
Đăng nhận xét