Hướng dẫn giải của Số lớn nhất
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
Từ xâu S chỉ lấy các chữ số, ghép lại thành số X sao cho X lớn nhất. Với |S| ≤ 10^6 cần thuật toán gần tuyến tính.
Sub 1: Vét cạn, sắp xếp đổi chỗ — ~O(n^2)~
Lấy hết chữ số trong S rồi sắp xếp giảm dần bằng bubble sort (đổi chỗ hai chữ số kề nhau khi sai thứ tự). Đúng ý tưởng "xếp các chữ số lớn lên trước", nhưng bubble sort O(n^2) quá chậm khi độ dài lên tới 10^6.
Kết quả chấm: 5/20 (SUB ok 5/20, TLE 15, WA 0)
#include <bits/stdc++.h>
using namespace std;
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
if (fopen("CAU2.INP", "r")) { freopen("CAU2.INP", "r", stdin); freopen("CAU2.OUT", "w", stdout); }
string s;
cin >> s;
// Lay tat ca chu so trong xau
string x = "";
for (char c : s)
if (isdigit(c)) x += c;
// Vet can: sap xep giam dan bang bubble sort (doi cho lien tiep), O(n^2)
int n = x.size();
for (int i = 0; i < n; i++)
for (int j = 0; j + 1 < n - i; j++)
if (x[j] < x[j + 1]) swap(x[j], x[j + 1]);
// Bo cac so 0 o dau (neu tat ca deu la 0 thi in 0)
int p = 0;
while (p + 1 < n && x[p] == '0') p++;
cout << x.substr(p) << "\n";
return 0;
}
Sub 2: Đếm tần suất các chữ số — ~O(n)~
Chỉ có 10 chữ số nên đếm số lần xuất hiện của mỗi chữ số 0..9 trong một lượt duyệt. Sau đó in lần lượt chữ số 9, 8, ..., 0 với số lần đếm được.
Bẫy: nếu mọi chữ số đều là 0 thì kết quả phải in "0", không in các số 0 đứng đầu.
Kết quả chấm: 20/20
#include <bits/stdc++.h>
using namespace std;
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
if (fopen("CAU2.INP", "r")) { freopen("CAU2.INP", "r", stdin); freopen("CAU2.OUT", "w", stdout); }
string s;
cin >> s;
// Dem so lan xuat hien cua tung chu so 0..9
int cnt[10] = {0};
for (char c : s)
if (isdigit(c)) cnt[c - '0']++;
// Ghep cac chu so theo thu tu giam dan de duoc so lon nhat
string ans = "";
for (int d = 9; d >= 0; d--)
ans += string(cnt[d], char('0' + d));
// Neu toan so 0 thi ket qua la 0 (bo bot so 0 o dau)
size_t p = ans.find_first_not_of('0');
if (p == string::npos) cout << "0\n";
else cout << ans.substr(p) << "\n";
return 0;
}
Bình luận