Nguồn đề bài: http://www.spoj.com/PTIT/problems/BCSAPXEP/
Nội dung bài viết
1. Đề bài sắp xếp bằng đếm phân phối
Sắp xếp dãy tăng dần.
Input
– Dòng đầu chứa số n ( số phần tử của dãy 1<=n<=1000)
– n dòng sau, mỗi dòng là 1 phần tử của dãy (giá trị tuyệt đối không quá 1000)
Output
Mỗi phần tử của dãy in trên 1 dòng, theo thứ tự tăng dần.
Lưu ý:
Đây là bài sắp xếp cơ bản. Bạn nên sử dụng nhiều thuật toán sắp xếp khác nhau để submit: Sắp xếp chọn, nổi bọt, chèn, quicksort, heapsort, hàm sort trong STL algorithm,….
Example
Input:
3
3
2
1
Output:
1
2
3
2. Code Sắp xếp bằng thuật toán đếm phân phối pascal
xem kỹ hơn về thuật toán: https://kienthuc24h.com/tim-hieu-va-cai-dat-thuat-toan-counting-sort/
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 | var DD:array[-1000..1000] of word; n,j:word; tam,i:integer; begin readln(n); fillchar(dd,sizeof(dd),0); for i:=1 to n do begin readln(tam); inc(dd[tam]); end; for i:=-1000 to 1000 do for j:=1 to dd[i] do writeln(i); end. |
độ phức tạp O(n).
BCSAPXEP spoj PTIT
Bài viết liên quan
- PTIT127C spoj ptit- Bố trí phòng họp
- P133SUMF spoj PTIT – cấp số cộng
- BCMARA spoj PTIT – Chạy đua marathon
- BCCOW spoj PTIT – Đi xem phim
- P152PROB PTIT spoj – Phân nhóm
- P153PROF PTIT spoj – Quyết chiến
- P151PROG spoj PTIT – Xếp Hàng
- PTIT123A PTIT spoj – Sắp xếp 2
- PTIT016E spoj PTIT – ACM PTIT 2016 E – Kỳ thi ACM/ICPC
- PTIT016D spoj PTIT- ACM PTIT 2016 D – Biểu thức