# **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;
}
angwangsushi
Created at
0 likes