# **Lưu ý: Hãy tự nghĩ cách giải, chỉ xem sol khi bí**
## **Ý TƯỞNG**:
***INPUT** n của đề bài có thể lên tới $10^{5000000}$*
$\Rightarrow$ ***Việc sử dùng kiểu dữ liệu `long long` hay `int` là không thể*. Thay vào đó, ta có thể sử dụng kiểu dữ liệu `string` để giải quyết bài toán.**
## $\Rightarrow $ Từ đó ta sẽ khai thác bài toán theo hướng:
* **Tạo một `string` n, duyệt qua n, chuyển từng `char` của n sang `int`**
* **Tạo 1 vector để lưu các số vừa chuyển đổi**
```
string n;
cin >> n;
vector<int> vec;
for(char c : n){
int chuso = c-'0';
vec.push_back(chuso);
}
```
* **Bây giờ chỉ cần dùng STL sort, để sắp xếp các phần tử của vector theo thứ tự từ bé đến lớn**
### CHÚ Ý:
**Sau khi đã sắp xếp, phần tử đầu tiên CÓ THỂ là số 0, trong khi đề bài yêu cầu số 0 không được đứng đầu**\
$\Rightarrow $ **Nên ta cần duyệt để xem vị trí của phần tử gần nhất lớn hơn 0, sử dụng hàm swap để hoán đổi phần tử đầu và phần tử đó.**
***
## **Độ phức tạp thuật toán**
*Với cách làm trên, **độ phức tạp thời gian là** O(n log n)*
***
**CODE THAM KHẢO* :*
```
#include <bits/stdc++.h>
#define ll long long
#define endl "\n"
#define FOR(i, l, r) for (int i = l; i <= r; i++)
#define fre(NAME) freopen(NAME".inp","r",stdin); freopen(NAME".out","w",stdout)
#define suyvolo ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL)
using namespace std;
int main(){
suyvolo;
string n;
cin >> n;
vector<int> vec;
for(char c : n){
int chuso = c-'0'; // chuyển từ char -> int
vec.push_back(chuso);
}
sort(vec.begin(),vec.end());
if(vec[0] == 0){ // Xét xem vị trí đầu có phải là số 0 hay không
for(ll i =1 ; i < vec.size();i++){
if(vec[i] > vec[0]){
swap(vec[0],vec[i]); // Hoán đổi vị trí
break;
}
}
}
for(ll num :vec) cout << num;
return 0;
}
# Lời giải chỉ tham khảo (Cpp)
### Nhận xét
- Số đề bài cho là tương đối lớn, ta không thể sử dụng kiểu dữ liệu số như int hay long long được, bài này ta sẽ dùng xâu để nhập dữ liệu
- Để tìm được một số min từ các chữ số đã cho thì **Hàng càng cao, số càng bé**
*Ví dụ có 2 số 1,9 thì*
```
hàng cao nhất là hàng chục ứng với 1
hàng bé nhất là hàng đơn vị ứng với 9
=> Số bé nhất từ 2 số là 19
```
### Xử lí
- Ta nhận thấy các chữ số chỉ từ 0 -> 9, nếu nhập chữ số đã cho ban đầu vào mảng rồi sắp xếp mảng thì sẽ mất O(n.log(n)) lận
- Nhưng bài này ta có cách giải chỉ O(n), thay vì lưu thành mảng chung, ta chỉ cần cộng một biến đếm số lượng chữ số a đã cho (0 <= a <= 9)
- Tiếp ta sẽ được một dãy đếm 10 phần tử đã được sắp xếp theo chỉ số từ 0 -> 9
- Việc còn lại là in lần lượt số lần xuất hiện của số đó từ 0 -> 9 thôi. Ez
p/s: Bài yêu cầu hàng cao nhất != 0 nữa đấy
Code mẫu
```cpp
void solve()
{
int cnt[10];
string s;
cin >> s;
for(char c : s)
{
cnt[c - '0']++; // Cách nhập đầu vào và chuyển char thành int
}
// Duyệt qua các chữ số xuất hiện và tìm xem số nào bé nhất xuất hiện khác 0 để làm hàng cao nhất
int val = 0;
for(int i = 1; i < 10; i++)
{
if(cnt[i] > 0)
{
cnt[i]--;
val = i;
break;
}
}
// Sau khi đảm bảo hàng cao nhất khác 0 thì điền các hàng còn lại thôi
cout << val;
for(int i = 0; i < 10; i++)
{
while(cnt[i]--)
{
cout << i;
}
}
}
```
angwangsushi
Created at
0 likes
Real_BeeYT
Created at
0 likes