PTIT061 - Sắp xếp mảng kiểu mới
Xem dạng PDF
Gửi bài giải
Điểm:
1,00 (OI)
Giới hạn thời gian:
1.0s
Giới hạn bộ nhớ:
256M
Tác giả:
Dạng bài
Ngôn ngữ cho phép
C, C#, C++, Go, Java, Pascal, Perl, PHP, Python, Ruby, Rust, Scratch, Swift
Cho mảng ~a~ chứa ~n~ số nguyên. Với mỗi phần tử ~a_i~ của mảng, bạn phải sắp xếp lại các chữ số của phần tử đó, sao cho giá trị ~a_i~ thu được sau khi sắp xếp các chữ số của nó là lớn nhất.Biết rằng chiều dài ~a_i~ trước và sau sắp xếp không thay đổi.
Sau đó in ra các phần tử của mảng theo chiều không tăng, mỗi phần tử cách nhau bởi một dấu cách.
Input
- Dòng đầu tiên chứa số nguyên dương ~n~ ( ~n \le 1000~ ).
- Dòng thứ hai chứa ~n~ số nguyên ~a_i~ là các phần tử của mảng a , các phần tử cách nhau bởi dấu cách ( ~|a_i| \le 10^4 ~).
Output
In ra các phần tử của mảng theo yêu cầu đề bài.
Sample
Input #1
10
61 947 6 96 534 2669 4 263 1449 77
Output #1
9662 9441 974 632 543 96 77 61 6 4
Problem source: CLB Lập Trình PTIT
Bình luận
Ý tưởng: Với bài này mình code theo kiểu sử dụng kết hợp giữa string và số. Ta sẽ nhập vào toàn bộ là các string
Thứ nhất: Dễ thấy số dương ở dạng xâu ký tự, để tìm cách sắp xếp lớn nhất thì ta chỉ việc sort theo chiều giảm dần của 1 xâu là được. Ví dụ 1023 -> sort theo chiều giảm dần -> 3210. Sau đó chuyển sang số nguyên rồi add vào mảng hay vector gì đó là được.
Thứ hai: Số âm sẽ ngược lại so với số dương (bỏ không xét ký tự đầu nhé vì nó là '-' mà), tức là ta sẽ sort theo chiều tăng dần. Ví dụ -321 -> sort theo chiều tăng dần -> -123.
Vấn đề ở đây đó là nếu sort theo chiều tăng dần, trong trường hợp gặp phải số âm có chứa số 0, kiểu như -32012 -> sort -> -01223 số này sai so với yêu cầu của bài toán vì khi chuyển sang số nguyên sẽ là -1223 (thiếu mất 1 chữ số, người ta chỉ cho sắp xếp chứ không cho phép bỏ bớt đi). Vậy để giải quyết việc này ta chỉ cần tìm chữ số != 0 đầu tiên trong dãy số âm đó đổi lên đầu là được. Vậy thực chất -32012 -> sort -> -01223 -> check + chuyển đổi -> -10223 (số 1 là số != 0 đầu tiên). Sau đó chuyển sang số rồi add vào mảng.
CƯỜNG GIẢ HỌ ĐINH, VẠN CỔ TỐI CƯỜNG. CAO CAO TẠI THƯỢNG, DUY NGÃ ĐỘC TÔN
case 8 làm như nào để ra được vậy mọi người, mình làm đầy đủ trường hợp số âm vs dương luôn rồi vẫn không ra được test case 8.
Bạn có thể thử nghiệm với test sau, 2 100101 -100101
111000 -000111 đúng không ạ!
111000 đúng, còn trường hợp số âm thì sai, phải là -100011 mới đúng. Vì số 0 đứng trước không có nghĩa, mà không có nghĩa thì ta sẽ bỏ đi (điều này sai so với yêu cầu của bài toán, người ta chỉ cho sắp xếp chứ không cho phép bỏ bớt đi). Để chuyển từ -000111 -> -100011 (0 chuyển chỗ cho 1) thì ta chỉ cần tìm phần tử đầu tiên != 0 trong số đổi lên vị trí đầu là được bạn nhé.
mình mắc ở case 8, mn cho mình xin ý tưởng tại case đó với ạ
Bn nhớ check cả TH số âm nữa đấy
đề bảo nguyên dương mà