Hướng dẫn giải của LIST16: Sắp xếp dãy theo tổng các chữ số
Chỉ dùng lời giải này khi không có ý tưởng, và đừng copy-paste code từ lời giải này. Hãy tôn trọng người ra đề và người viết lời giải.
Nộp một lời giải chính thức trước khi tự giải là một hành động có thể bị ban.
Nộp một lời giải chính thức trước khi tự giải là một hành động có thể bị ban.
Hướng dẫn giải
Sắp xếp dãy ~n~ số nguyên dương tăng dần theo tổng các chữ số của mỗi số.
Lưu ý quy ước: các số có cùng tổng chữ số giữ nguyên thứ tự ban đầu trong dãy (khớp ví dụ: 12 đứng trước 3).
Sub 1: Chọn dần (selection sort) — ~O(n^2)~, dùng khi ~n \le 1000~
Với mỗi vị trí, tìm phần tử có tổng chữ số nhỏ nhất trong phần còn lại rồi đưa về vị trí đó. Dùng phép xoay đoạn để các phần tử khác giữ đúng thứ tự tương đối.
Nếu chỉ nộp sub này: đúng 9/20 test.
Sub 2: Sắp xếp ổn định — ~O(n \log n)~, dùng khi mọi trường hợp còn lại
Tính tổng chữ số của từng số một lần, rồi sắp xếp cặp (tổng chữ số, số) theo khóa tổng chữ số bằng sắp xếp ổn định, nên các số có cùng tổng giữ thứ tự ban đầu.
Nếu chỉ nộp sub này: đúng 20/20 test.
Chương trình hoàn chỉnh
Đề không chia subtask. Sub 1 là sắp xếp chọn dần, sub 2 là sắp xếp bằng thư viện.
Chương trình đọc ~n~ và dãy. Nếu ~n \le 1000~ thì gọi sub1, ngược lại gọi sub2.
#include <bits/stdc++.h>
using namespace std;
int n;
vector<long long> a;
// Tong chu so cua x (x duong)
int tongChuSo(long long x) {
int s = 0;
while (x > 0) { s += x % 10; x /= 10; }
return s;
}
// Sub 1: selection sort on dinh (chon phan tu co tong chu so nho nhat, lay cai dau tien neu bang nhau)
// O(n^2) voi n <= 1000. rotate giu thu tu tuong doi cua cac phan tu khac.
void sub1() {
for (int i = 0; i < n; i++) {
int best = i;
for (int j = i + 1; j < n; j++)
if (tongChuSo(a[j]) < tongChuSo(a[best])) best = j;
rotate(a.begin() + i, a.begin() + best, a.begin() + best + 1);
}
}
// Sub 2: sap xep on dinh theo tong chu so, O(n log n) voi sort on dinh (giu thu tu ban dau khi bang nhau)
void sub2() {
vector<pair<int, long long>> v(n);
for (int i = 0; i < n; i++) v[i] = make_pair(tongChuSo(a[i]), a[i]);
stable_sort(v.begin(), v.end(),
[](const pair<int, long long> &p, const pair<int, long long> &q) { return p.first < q.first; });
for (int i = 0; i < n; i++) a[i] = v[i].second;
}
int main() {
cin >> n;
a.resize(n);
for (int i = 0; i < n; i++) cin >> a[i];
if (n <= 1000) sub1();
else sub2();
for (int i = 0; i < n; i++) cout << a[i] << (i + 1 < n ? ' ' : '\n');
return 0;
}
Bình luận