Link Sub: http://www.spoj.com/PTIT/problems/PTIT125I/
Người Gửi: Dương Lee
- Problem:
Cho một số có N chữ số. Bạn hãy xóa đi K chữ số để được số còn lại sau khi xóa là lớn nhất có thể.Input
- Dòng 1: số N và K (1<=K<N<=500 000).
- Dòng 2: Số có N chữ số, bắt đầu bằng số khác 0.
Output
- Số lớn nhất có thể sau khi xóa K chữ số.
Example:
- Số lớn nhất có thể sau khi xóa K chữ số.
Input
4 2
1924
Output:
94
- Solution:
Nhận thấy khi xóa đi mà số vẫn lớn nhất thì mỗi lần xóa một chữ phải tạo ra số lớn nhất.
VD: 1924
-> Xóa lần 1 -> 924 max
-> Xóa lần 2 -> 94 max.
Vậy áp dụng stack để tạo dãy tuyến tính không tăng (khi còn xóa được). Dãy đó luôn là dãy lớn nhất có thể tạo được khi xóa.
EX: 170803 (K=3)
S: 1 (K=3)
S: 7 (K=2 (xóa 1))
S: 7 0 (K=2)
S: 8 (K=0 (xóa 7, 0))
S: 8 0 (K=0)
S: 8 0 3 (K=0)
-> 803 max.
- Code:
C++:
https://ideone.com/8ZXdyM
#include <iostream>
#include <stack>
#include <vector>
using namespace std;
int main ()
{
long N, K;
cin>>N>>K;
stack <int> S;
for (long i=1; i<=N; i++)
{
char tmp_char;
cin>>tmp_char;
int tmp_int = tmp_char - '0';
if (S.empty())
{
S.push(tmp_int);
}
else
{
while (!S.empty() && tmp_int > S.top() && K>0)
{
S.pop();
K--;
}
S.push(tmp_int);
}
}
while (K>0 && !S.empty())
{
S.pop();
K--;
}
vector <int> smallest;
while (!S.empty())
{
int tmp=S.top();
S.pop();
smallest.push_back(tmp);
}
for (long i=smallest.size()-1; i>=0; i--)
cout<<smallest[i];
return 0;
}