Xóa Chữ Số (DELNUM)
Đề bài
Hãng cung cấp dịch vụ điện thoại XYZ khuyến khích nhiều người đăng kí thuê bao bằng cách: Khi khách hàng đến đăng kí thuê bao thì sẽ được cấp hai số may mắn là số nguyên dương $n$ và $k$, hãng sẽ khuyến mại người đó một số tiền nhận được từ số $n$ sau khi xóa đúng $k$ chữ số ($k$ nhỏ hơn số chữ số của $n$). Hải vừa mới đăng kí thuê bao của hãng và được cung cấp hai số $n$ và $k$.
Yêu cầu: Bạn hãy giúp Hải xóa đi $k$ chữ số của số $n$ để số nhận được số tiền là lớn nhất.
Dữ liệu vào:
- Dòng thứ nhất là số $n$ (số chữ số của $|n| \le 10^6$).
- Dòng thứ hai là số $k$ $(k < n)$.
Kết quả:
- Một dòng duy nhất là số lớn nhất có được sau khi xóa đi $k$ chữ số của $n$.
58816
28862357111317192329
67317192329Giải thích ví dụ 1: từ 58816 xóa chữ số 5 và chữ số 1 thì còn lại 886, đây là số lớn nhất có thể.
Lời mở đầu
Bài này mình được một bạn học viên hỏi nên sẵn tiện mình viết bài giải chi tiết để nhiều bạn được tham khảo luôn. Hy vọng mang đến được giá trị cho các bạn 😇.
Link này công khai, bạn nào muốn thử nộp bài để hệ thống chấm xem có đúng hay không thì dùng link này nhé. Chưa có tài khoản thì tạo tài khoản rồi đăng nhập nộp bài thử hen.
Nộp bài trên LQDOJBài đăng gần nhất trước bài này mình có đăng bài Mật khẩu (PASSW – HSG 16.17), nó như là phiên bản cơ bản của bài này. Trong bài này phần đầu tiên mình sẽ nói tiếp về cách làm của bài đó, đem áp dụng qua bài này và phát triển sửa đổi lên như thế nào để AC được, rồi sau đó mình mới nói thêm các cách khác để AC bài này. Nên bạn nào chưa đọc bài Mật khẩu thì nên xem qua trước để hiểu cách thức mình đã hướng dẫn trong bài đó, rồi xem tiếp bài này mới hiểu được nha.
Lộ trình lời giải, bấm vào từng phần để nhảy tới:
Ý tưởngXóa K chữ số = chọn L − K chữ số
Thì cũng đã có bạn học viên của mình sau khi làm được bài trước đó xong, qua bài này lại không nhìn ra điểm tương đồng của 2 bài. Còn các bạn thì sao?
Để mình nói cho bạn nào chưa thấy sự tương đồng nhé. Bài trước đó ta có chuỗi số $S$ có độ dài $L$ và cần chọn ra $K$ chữ số theo đúng thứ tự từ trái qua phải sao cho số có $K$ chữ số đó là số lớn nhất có thể. Còn ở bài này ta cũng có chuỗi số $S$ có độ dài $L$ nhưng không phải là chọn mà là ta sẽ xóa đi $K$ chữ số để phần còn lại là số lớn nhất có thể.
Vậy điểm tương đồng ở đây các bạn xem nhé: giả sử $L = 10$, cần xóa $K = 3$ chữ số để còn lại 7 chữ số là số lớn nhất có thể. Vậy có phải nó chính là bài toán hãy chọn ra 7 chữ số sao cho tạo ra được số lớn nhất có thể không? Tức là code của bài kia đem qua bài này chỉ cần sửa lại chỗ chọn $K$ chữ số giờ đây sẽ là $L - K$, đơn giản là vậy thôi.
À tất nhiên điểm khác nữa là bài này cho sẵn từ đầu chuỗi $S$ chỉ toàn là ký tự chữ số thôi, chứ không như bài kia ta phải duyệt chuỗi $S$ để tạo ra chuỗi str chứa các ký tự chữ số; cũng như bài này không cần phải kiểm tra tính đối xứng gì hết, chỉ cần trả về kết quả lớn nhất. Nên ta xóa bớt những xử lý dư thừa bên bài kia nhé.
Cách 1Đem nguyên code bài Mật khẩu qua – O(K·(N − K)) – TLE test 11
Nhắc lại nhanh tư tưởng tham lam của bài trước: cần chọn $k$ chữ số thì lần chọn đầu tiên chỉ được chọn trong đoạn từ start = 0 đến finish = L − k (để phía sau còn đủ chữ số cho các lần chọn sau). Trong đoạn đó chọn chữ số lớn nhất, nếu có nhiều chữ số lớn nhất thì lấy chữ số ở vị trí nhỏ nhất. Sau mỗi lần chọn: start = idxMax + 1, finish++, k--. Nếu từ start đến cuối chuỗi còn đúng k ký tự thì lấy hết luôn.
Vậy code bài kia ta sửa lại như sau là có thể nộp với bài này:
#include <bits/stdc++.h>
using namespace std;
string MaxNum(string s, int k){
string res = "";
int start = 0, finish = (int)s.length() - k;
while(k != 0){
if((int)s.length() - start == k){
res += s.substr(start);
break;
}
int idxMax = start;
for(int i = start + 1; i <= finish; ++i){
if(s[i] > s[idxMax]){
idxMax = i;
}
}
res.push_back(s[idxMax]);
start = idxMax + 1;
finish++;
k--;
}
return res;
}
int main() {
ios::sync_with_stdio(0);
cin.tie(0);
string s;
int k;
cin >> s >> k;
cout << MaxNum(s, s.length() - k);
return 0;
}s = input()
k = int(input())
def max_num(s, k):
res = ""
start = 0
finish = len(s) - k
while k > 0:
if len(s) - start == k:
res += s[start:]
break
idx_max = start
for i in range(start + 1, finish + 1):
if s[i] > s[idx_max]:
idx_max = i
res += s[idx_max]
start = idx_max + 1
finish += 1
k -= 1
return res
print(max_num(s, len(s) - k))Như các bạn đã thấy, ta giữ nguyên hàm MaxNum không thay đổi, chỉ sửa lại chỗ truyền tham số k của hàm thành s.length() - k, và trong hàm main ta đơn giản hóa bước đọc dữ liệu cũng như những xử lý dư thừa mình đã nói ở trên.
Thì code ở trên mình thử nộp thì nó AC 10/11 test. Ở test 11 thì bị TLE (chạy quá thời gian cho phép). Điều này ở cuối bài trước đó mình đã có dự báo trước rồi đó các bạn. Tại vì độ phức tạp của bước xử lý là $O(K \cdot (N - K))$ với $N$ là độ dài chuỗi, $K$ là số ký tự lựa chọn. Các bạn thử xem với bài này $N$ tối đa có thể là $10^6$, $K$ giờ đây là số ký tự xóa chứ không phải là số ký tự chọn, hãy giả sử $K = N/2$ như thế số ký tự chọn cũng là $N/2$. Vậy thì $5 \cdot 10^5 \cdot 5 \cdot 10^5 = 25 \cdot 10^{10}$ = 250 tỷ, đã vượt quá xa ngưỡng giới hạn 1 giây cao lắm là $10^8$ tức là 100 triệu, cụ thể nó gấp cả 2.500 lần nên không bị TLE mới sợ haha.
Cách 2Mảng vị trí của từng chữ số + lower_bound – O(N log N) – AC
Thì để không bị TLE ta phải xem xét cải tiến lại thuật toán sao cho tốt hơn. Nhìn vào thuật toán hiện tại, ta thấy cách nó xử lý là: lặp đủ $K$ lần (có thể kết thúc sớm nếu rơi vào trường hợp đặc biệt), mỗi lần chọn 1 ký tự. Rồi với mỗi lần lặp đó đi tìm trong đoạn từ start đến finish vị trí ký tự số lớn nhất, nếu có nhiều hơn 1 ký tự số lớn nhất thì trả về vị trí nhỏ nhất.
Rõ ràng việc lặp $K$ lần là không thể tối ưu hơn được, tại vì ta đang cần chọn ra $K$ ký tự nên lặp $K$ lần mỗi lần chọn 1 ký tự là hợp lý, và ta cũng đã có trường hợp đặc biệt kết thúc sớm rồi.
Tiếp đó các bạn sẽ thấy cách ta đang tìm kiếm ký tự số thỏa mãn trong đoạn start đến finish là tìm kiếm tuyến tính (Linear Search), cứ phải xét tuần tự từ đầu đến cuối đoạn, tức là $O(N)$. Khi nói đến cải tiến việc tìm kiếm thì cơ bản chỉ có 2 thuật toán tìm kiếm phổ biến là tìm kiếm tuyến tính và tìm kiếm nhị phân (Binary Search). Vậy hãy thử suy nghĩ xem có thể dùng tìm kiếm nhị phân để có $O(\log N)$ không?
Ta để ý thấy rằng các ký tự số trong đoạn từ start đến finish suy cho cùng cũng chỉ có 10 trường hợp là các ký tự từ '0' đến '9' thôi. Nên ta sẽ dùng một mảng 2 chiều có 10 dòng, mỗi dòng có số lượng phần tử không cố định: dòng 0 là mảng chứa các vị trí của ký tự '0' xuất hiện trong chuỗi, dòng 1 chứa các vị trí của ký tự '1', … cứ thế cho đến dòng 9. Ví dụ ở test mẫu 2:
| Dòng (chữ số) | Các vị trí xuất hiện (tăng dần) |
|---|---|
| 0 | (rỗng) |
| 1 | 4 5 6 8 10 |
| 2 | 0 12 14 |
| 3 | 1 7 13 |
| 4 | (rỗng) |
| 5 | 2 |
| 6 | (rỗng) |
| 7 | 3 9 |
| 8 | (rỗng) |
| 9 | 11 15 |
Nếu để ý các bạn sẽ thấy các vị trí trên mỗi dòng đang theo thứ tự tăng dần (bởi vì ta duyệt chuỗi từ đầu đến cuối để thống kê ra mà), vì có thứ tự nên ta áp dụng được tìm kiếm nhị phân chỗ này.
Khi cần tìm trong đoạn từ start đến finish vị trí nhỏ nhất của ký tự lớn nhất, ta sẽ xét ngược từ dòng 9 về dòng 0 để đảm bảo tìm từ ký tự chữ số lớn nhất trở về. Với mỗi dòng ta dùng lower_bound (hàm này truyền vào vị trí bắt đầu tìm, vị trí kết thúc tìm, phần tử cần tìm $x$, và trả về vị trí đầu tiên trong đoạn chỉ định mà thỏa mãn $\ge x$) với phần tử cần tìm là start, để xem trên dòng đó có phần tử nào $\ge$ start không:
- Nếu không tồn tại: trên dòng đó toàn các vị trí nhỏ hơn
start, chắc chắn không có vị trí nào nằm trong đoạn → xét dòng tiếp theo. - Nếu tồn tại: kiểm tra vị trí đầu tiên đó có $\le$
finishkhông? Chỗ này các bạn lưu ý nhé, phải nhớ mình còn bị ràng buộc vớifinishnữa. Nếu không thỏa thì xét dòng tiếp theo, còn nếu thỏa thì vị trí đó hợp lệ, ta kết thúc việc duyệt:resthêm ký tự tương ứng với dòng đang xét (dòng 9 thì thêm'9', dòng 8 thì thêm'8'…), rồistart= vị trí tìm thấy + 1,finish++, mọi thứ tiếp tục như mặc định.
Source code để các bạn tham khảo nếu làm theo hướng này:
#include <bits/stdc++.h>
using namespace std;
string MaxNum(string s, int k){
vector<vector<int>> a(10);
for(int i = 0; i < (int)s.length(); ++i){
a[s[i] - '0'].push_back(i);
}
string res = "";
int start = 0, finish = (int)s.length() - k;
while(k != 0){
if((int)s.length() - start == k){
res += s.substr(start);
break;
}
for(int i = 9; i >= 0; --i){
auto it = lower_bound(a[i].begin(), a[i].end(), start);
if(it != a[i].end()){
int idx = it - a[i].begin();
if(a[i][idx] <= finish){
res.push_back(i + 48);
start = a[i][idx] + 1;
finish++;
k--;
break;
}
}
}
}
return res;
}
int main() {
ios::sync_with_stdio(0);
cin.tie(0);
string s;
int k;
cin >> s >> k;
cout << MaxNum(s, s.length() - k);
return 0;
}import sys
import bisect
def MaxNum(s, keep):
a = [[] for _ in range(10)]
for i, ch in enumerate(s):
a[int(ch)].append(i)
res = []
start = 0
finish = len(s) - keep
while keep != 0:
if len(s) - start == keep:
res.append(s[start:])
break
for digit in range(9, -1, -1):
idx = bisect.bisect_left(a[digit], start)
if idx < len(a[digit]):
pos = a[digit][idx]
if pos <= finish:
res.append(str(digit))
start = pos + 1
finish += 1
keep -= 1
break
return "".join(res)
data = sys.stdin.read().strip().split()
s = data[0]
k = int(data[1])
print(MaxNum(s, len(s) - k))Giải thích một số chỗ trong code ở trên:
- Chỗ biến
auto it: bản chất mình dùng từ khóaautođể compiler tự xác định đúng kiểu dữ liệu cho con trỏit, nếu viết đầy đủ sẽ làvector<int>::iterator itnha các bạn. À phải nói cho bạn nào không biết,itlà tên biến mình đặt thôi (viết tắt của iterator), các bạn muốn đặt tên gì là tùy các bạn nha. - Chủ yếu là các bạn phải hiểu về hàm
lower_boundthì xem đoạn code trên mới hiểu, nên bạn nào chưa biết về hàm này thì cứ Google từ khóa lower_bound rồi xem các bài viết trên GeeksforGeeks là rõ.res.push_back(i + 48)là thêm ký tự có mã ASCII $i + 48$, tức là ký tự chữ số'0' + i. - Phần mảng 2 chiều mình dùng kiểu
vectorcho tiện, nếu bạn nào không dùngvectorthì phải tự khai báo con trỏ cấp phát động mảng 2 chiều nhé, chứ không dùng mảng 2 chiều tĩnh chỗ này được vì số lượng phần tử trên mỗi dòng không đồng đều nhau.
Đánh giá độ phức tạp:
- Không gian: $O(N)$ của chuỗi $s$ + $O(N)$ của mảng 2 chiều (tổng số phần tử của cả 10 dòng đúng bằng $N$). Tổng quát vẫn là $O(N)$.
- Thời gian: $O(N)$ đọc chuỗi + $O(N)$ tạo mảng 2 chiều + bước xử lý lặp $K$ lần, mỗi lần trường hợp xấu nhất phải tìm kiếm nhị phân trên đủ cả 10 dòng, tức là $O(K \cdot \log N)$ (hằng số 10 bỏ qua). Cho trường hợp xấu nhất $K = N/2$: $O(2N) + O(0{,}5 \cdot N \log N)$, theo quy tắc nhân và cộng Big-O thì tổng quát là $O(N \log N)$.
Với $N = 10^6$ thì $N \log_2 N \approx 20 \cdot 10^6 = 2 \cdot 10^7$, ít hơn ngưỡng 1 giây $(3 \text{ đến } 5) \cdot 10^7$ hay cao lắm là $10^8$ từ 2 đến 5 lần nên không sợ bị TLE. Các bạn thử nộp thì sẽ thấy giờ đây sẽ AC được test cuối với cách làm này nhé.
Cách 3Đi theo đúng tư tưởng xóa: vét cạn + tham lam – O(N³)
Tuy ta đã AC được bài này với cách làm trên, nhưng mình cũng nói luôn là đó chưa phải là cách làm tối ưu nhất. Cách làm tối ưu nhất cho bài này độ phức tạp thời gian chỉ là $O(N)$ thôi (nói chính xác hơn là $O(N + K)$ nhưng theo quy tắc cộng Big-O ta kết luận $O(N)$). Trước khi nói đến cách tối ưu đó thì ta thử giải quyết bài này nhưng không đi theo tư tưởng chọn mà đi theo đúng tư tưởng xóa như đề bài đưa ra.
Một tư tưởng đơn giản nhất là vét cạn kết hợp thêm 1 chút tham lam: chuỗi ban đầu có độ dài $L$ thì ta có thể xóa đi 1 ký tự bất kỳ trong $L$ vị trí. Ta thử xóa lần lượt từng vị trí, mỗi lần xóa thu được 1 chuỗi còn lại, và tìm ra chuỗi lớn nhất trong tất cả các chuỗi còn lại đó. Lấy chuỗi lớn nhất đó tiếp tục cho lần xóa 1 ký tự tiếp theo, lại tìm chuỗi còn lại lớn nhất, cứ thế sau khi xóa đủ $K$ lần thì chuỗi còn lại chính là đáp án.
Source code để các bạn tham khảo nếu làm theo hướng này:
#include <bits/stdc++.h>
using namespace std;
string MaxNum(string s, int k){
string Max = s;
while(k--){
string temp = s;
s.erase(s.begin());
Max = s;
s = temp;
for(int i = 1; i < (int)s.length(); ++i){
s.erase(s.begin() + i);
Max = max(Max, s);
s = temp;
}
s = Max;
}
return Max;
}
int main() {
ios::sync_with_stdio(0);
cin.tie(0);
string s;
int k;
cin >> s >> k;
cout << MaxNum(s, k);
return 0;
}import sys
def MaxNum(s, k):
Max = s
while k > 0:
temp = s
# xóa ký tự đầu tiên
s = s[1:]
Max = s
s = temp
for i in range(1, len(s)):
s = s[:i] + s[i+1:]
if s > Max:
Max = s
s = temp
s = Max
k -= 1
return Max
data = sys.stdin.read().strip().split()
s = data[0]
k = int(data[1])
print(MaxNum(s, k))Giải thích: vì ta xóa 1 ký tự trong chuỗi s tức là đã làm nó bị thay đổi, nên trước đó phải có chuỗi tạm temp = s để lưu lại, rồi sau mỗi lần xóa thì s nhận lại giá trị từ temp để trở về trạng thái trước khi xóa, chuẩn bị cho lần xóa tiếp theo. Biến Max ban đầu lưu chuỗi s sau khi xóa ký tự ở vị trí 0, sau đó vòng lặp xét từ vị trí 1 đến cuối, lần lượt xóa từng ký tự rồi so sánh với Max để cập nhật. Trước khi sang lần xóa mới ta gán s = Max để lần sau xét trên chuỗi lớn nhất có được sau khi xóa 1 ký tự, đây là tư tưởng của tham lam. Cứ thế sau cùng Max chính là chuỗi kết quả.
Đánh giá độ phức tạp: không gian $O(N)$ (chuỗi s, temp, Max). Thời gian: vòng lặp chạy $K$ lần, mỗi lần xét lần lượt từng ký tự trong chuỗi, mà thao tác xóa (và cả phép gán, so sánh chuỗi) trường hợp xấu nhất là $O(N)$. Nếu $K = N/2$ thì về mặt lý thuyết là $O(N^3)$.
Và như các bạn thấy $O(N^3)$ còn tệ hơn $O(N^2)$ của cách làm theo tư tưởng chọn ở Cách 1, nên Cách 1 chỉ bị TLE ở test cuối (test 11) còn cách này bị TLE từ test 9 luôn rồi (cụ thể các test 9, 10, 11). Có đúng như điều mình đã từng nói trong bài trước là nếu có thể tránh đụng đến việc xóa thì nên tránh không? Vì nó sẽ dẫn tới độ phức tạp lớn.
Thực ra code ở trên ta có thể sửa lại một chút trông sẽ gọn hơn (độ phức tạp vẫn vậy thôi). Thay vì dùng erase rồi phải lưu sang chuỗi tạm rồi khôi phục lại, nhìn rất rối rắm, ta có thể tạo ra chuỗi kết quả sau khi xóa vị trí i mà không cần tác động lên chính chuỗi s, bằng hàm substr:
- Chuỗi
ssau khi xóa ký tự 0:s.substr(1), tức là lấy hết chuỗistừ vị trí 1 đến cuối. - Chuỗi
ssau khi xóa vị tríi:s.substr(0, i) + s.substr(i + 1). Trong đós.substr(0, i)là lấy từ vị trí 0 và lấy đủiký tự (tức là từ đầu đến vị tríi − 1), còns.substr(i + 1)là lấy từ vị tríi + 1đến cuối, rồi phép+nối 2 chuỗi đó lại, nghĩa là đã bỏ đi đúng vị tríi.
#include <bits/stdc++.h>
using namespace std;
string MaxNum(string s, int k){
string Max = s;
while(k--){
Max = s.substr(1);
for(int i = 1; i < (int)s.length(); ++i){
Max = max(Max, s.substr(0, i) + s.substr(i + 1));
}
s = Max;
}
return Max;
}
int main() {
ios::sync_with_stdio(0);
cin.tie(0);
string s;
int k;
cin >> s >> k;
cout << MaxNum(s, k);
return 0;
}import sys
def MaxNum(s, k):
Max = s
while k > 0:
Max = s[1:] # bỏ ký tự đầu tiên
for i in range(1, len(s)):
candidate = s[:i] + s[i+1:]
if candidate > Max:
Max = candidate
s = Max
k -= 1
return Max
data = sys.stdin.read().strip().split()
s = data[0]
k = int(data[1])
print(MaxNum(s, k))Lúc này đây các bạn xem lại hàm MaxNum trông sẽ gọn hơn rất nhiều đúng không ^^
Cách 4Ngăn xếp (stack) – O(N) – tối ưu nhất
Rồi thì giờ mình nói qua về cách làm tối ưu nhất cho bài này theo tư tưởng xóa, cụ thể nó cũng có chút tham lam giống như cách làm ở trên. Ta sẽ cần sử dụng cấu trúc dữ liệu stack (ngăn xếp), bạn nào chưa biết về nó thì phải tìm hiểu trước để có kiến thức thì mới xem hiểu tiếp những gì dưới đây nha.
- Đầu tiên khi ngăn xếp rỗng thì ta cứ bỏ ký tự đầu tiên bên trái của chuỗi vào.
- Xét từ ký tự tiếp theo trở đi, với mỗi ký tự
s[i]: nếu stack không rỗng, đồng thời k > 0 (còn xóa được), đồng thời s[i] > st.top() (chữ số đang xét lớn hơn phần tử đầu stack) thì tak--vàst.pop()(xóa phần tử đầu stack đi). Vòng lặp cứ lặp liên tục đến khi stack rỗng, hoặck == 0, hoặcs[i] <= st.top()thì dừng, rồi ta đưas[i]vào stack. - Sau cùng lấy các phần tử của stack ra. Lưu ý stack là LIFO (Last In First Out) nên thứ tự đang bị ngược, vì thế chuỗi kết quả phải đảo ngược lại.
- Vẫn có thể
k > 0chưa về 0: trường hợp này xảy ra khi các ký tự còn lại trong stack theo thứ tự giảm dần (không ai "đẩy" được ai). Lúc này ta xóa đi $k$ ký tự cuối cùng của chuỗi kết quả (bởi nó là các chữ số nhỏ nhất).
Em nhập số và $k$ rồi bấm Tiếp để xem từng chữ số "đẩy" các chữ số nhỏ hơn ra khỏi ngăn xếp như thế nào:
Source code để các bạn tham khảo nếu làm theo hướng này:
#include <bits/stdc++.h>
using namespace std;
string MaxNum(string s, int k){
stack<char> st;
for(int i = 0; i < (int)s.length(); ++i){
while(!st.empty() && k > 0 && s[i] > st.top()){
k--;
st.pop();
}
st.push(s[i]);
}
s = "";
while(!st.empty()){
s.push_back(st.top());
st.pop();
}
reverse(s.begin(), s.end());
return s.substr(0, s.length() - k);
}
int main() {
ios::sync_with_stdio(0);
cin.tie(0);
string s;
int k;
cin >> s >> k;
cout << MaxNum(s, k);
return 0;
}import sys
def MaxNum(s, k):
st = []
for ch in s:
while st and k > 0 and ch > st[-1]:
k -= 1
st.pop()
st.append(ch)
# tạo lại chuỗi
s = "".join(st)
# cắt bớt nếu vẫn còn k
return s[:len(s) - k]
data = sys.stdin.read().strip().split()
s = data[0]
k = int(data[1])
print(MaxNum(s, k))Giải thích: kiểu dữ liệu trong stack là char vì stack chứa các ký tự. Khúc sau cùng ta reset lại chuỗi s = "" với mục đích lấy luôn chuỗi s làm chuỗi kết quả: push_back từng ký tự từ stack lấy ra vào s, đảo ngược lại, và như mình có nói để đề phòng k vẫn còn nên lấy s.substr(0, s.length() - k): nếu k = 0 thì lấy đủ toàn bộ chuỗi, còn nếu k > 0 thì bỏ đi $k$ ký tự cuối chuỗi.
Không khó để các bạn nhận ra tư tưởng tham lam và sự chính xác của cách làm trên đúng không? Nói đơn giản: để chuỗi kết quả là lớn nhất thì các ký tự trong chuỗi phải "cố gắng" theo thứ tự giảm dần, nên khi phát hiện có ký tự nào lớn hơn các ký tự trước đó mà vẫn còn có thể xóa được thì cứ xóa các ký tự nhỏ phía trước đi để đưa ký tự lớn đó lên trước.
Đánh giá độ phức tạp: không gian $O(N)$ của chuỗi $s$ + $O(N)$ của stack. Thời gian: vòng for chạy hết $N$ ký tự, tuy bên trong có lồng vòng while nhưng xét kỹ các bạn sẽ thấy mỗi lần while chạy là 1 lần k--, nên tổng cộng nó chỉ lặp tối đa $K$ lần rồi thôi. Vậy bước xử lý là $O(N + K)$, cộng bước lấy từng phần tử của stack ra $O(N - K)$ và bước đảo chuỗi $O(N - K)$. Tổng quát lại là $O(N)$, tốt hơn $O(N \log N)$ của Cách 2, nên đây là cách tối ưu nhất các bạn nhé.
Cài đặt bằng mảng (chuỗi) thay cho stack
Về mặt tư tưởng cài đặt ở trên, nếu bạn nào không dùng stack thì có thể dùng mảng 1 chiều để cài đặt, nó sẽ tối ưu hơn 1 chút (về mặt lý thuyết độ phức tạp thì không thay đổi), vì khúc sau cùng ta không cần phải lấy từng phần tử từ stack ra rồi đảo ngược lại mà có thể xuất kết quả từ mảng ra luôn. Ở đây mình dùng luôn chuỗi res làm "mảng":
#include <bits/stdc++.h>
using namespace std;
string MaxNum(string s, int k){
string res;
for(int i = 0; i < (int)s.length(); ++i){
while(res.size() > 0 && k > 0 && s[i] > res.back()){
k--;
res.pop_back();
}
res.push_back(s[i]);
}
return res.substr(0, res.length() - k);
}
int main() {
ios::sync_with_stdio(0);
cin.tie(0);
string s;
int k;
cin >> s >> k;
cout << MaxNum(s, k);
return 0;
}import sys
def MaxNum(s, k):
res = []
for ch in s:
while res and k > 0 and ch > res[-1]:
k -= 1
res.pop()
res.append(ch)
return "".join(res[:len(res) - k])
data = sys.stdin.read().strip().split()
s = data[0]
k = int(data[1])
print(MaxNum(s, k))res.back() là lấy ra ký tự cuối cùng của chuỗi res, res.pop_back() là xóa đi ký tự cuối cùng, res.push_back(...) là thêm ký tự vào cuối chuỗi. Mình nói sợ bạn nào không biết hehe.