描述
题解
可以用RMQ搞搞,这里需要说的是,给了一个n位数,去掉m位数,那么可以肯定的是1到m+1区间中最小的数必定是第一位,记第一位数位为pos(第一步),那么pos+1到m+2中的最小的数必定是第二个数字(第二步),以此类推,贪心查找。这也很好理解的,因为最极端的可能就是,第一步,m+1后的几位全部是留下来的,第二步,m+2后的几位全部是留下来的……
这里使用RMQ也行,不使用直接贪心也行,思路都是大差不差的。
代码
#include <iostream>
#include <cstring>
#include <string>
using namespace std;
int main()
{
string s;
int m;
while (cin >> s >> m)
{
int len = (int)s.length();
int p = 0;
int tmp_pos = m;
int flag = 0;
for (int i = 0; i < len - m; i++)
{
char mmin = s[p];
for (int j = p + 1; j <= tmp_pos; j++)
{
if (s[j] < mmin)
{
mmin = s[j];
p = j;
}
}
tmp_pos++;
p++;
if (!flag)
{
if (mmin == '0')
{
continue;
}
else
{
cout << mmin;
flag = 1;
}
}
else
{
cout << mmin;
}
}
if (!flag)
{
cout << "0";
}
cout << endl;
}
return 0;
}