Link Sub: http://www.spoj.com/PTIT/problems/P165PROA/
Người Gửi: Winner
- Problem:
1 con sâu chiều dài n sẽ được biểu diễn dưới dạng 1 xâu có n chữ cái: s[0], s[1], …, s[n-1].
Một con sâu con của 1 con sâu sẽ được biểu diễn dưới dạng xâu: s[p1], s[p2], …, s[pk] (1 <= p1 < p2 < … < pk <= n-1).
Cho 1 xâu là biểu diễn của 1 con sâu, tìm biểu diễn của con sâu con thứ tự cao nhất trong từ điển,
1 xâu x (x[0], x[1], …, x[n-1]) có thứ tự từ điển cao hơn xâu y (y[0], y[1], …, y[m-1]) khi và chỉ khi n > m và x[0]=y[0], x[1]=y[1], …, x[m-1]=y[m-1]; hoặc x[0]=y[0], x[1]=y[1], … x[r] = y[r] và x[r+1] > y[r+1]. Các ký tự được so sánh theo bảng mã ASCII.
InputDòng duy nhất bao gồm 1 xâu ký tự có chiều dài không quá 105.
Output
In ra trên 1 dòng duy nhất xâu ký tự là kết quả của bài toán
Example:
In ra trên 1 dòng duy nhất xâu ký tự là kết quả của bài toán
Input
ababba
Output:
bbba
Input
laptrinhtutraitim
Output:
uttm
- Solution:
- Nhập vào chuỗi kí tự và đánh dấu luôn vị trí của nó.
- Sắp xếp chuỗi theo định dạng: kí tự sắp xếp giảm dần, nếu kí tự tương đương thì sắp xếp vị trí tăng dần.
- In ra từng kí tự có vị trí lớn hơn vị trí trước đó trong xâu đã sắp xếp.Input
laptrinhtutraitim
Output:
uttm
(SX dưới đây sử dụng thư viện có sẵn là heap sort - Bạn nên tìm hiểu trước hoặc biết cách cài đặt)