AcWing 1453. 移掉K位数字
原题链接
中等
作者:
懋士月
,
2021-11-26 06:07:57
,
所有人可见
,
阅读 119
#include <iostream>
#include <string>
#include <cmath>
#include <vector>
#include <algorithm>
using namespace std;
typedef pair<int, int> PII;
const int N = 100005, M = 18;
PII vals[N];
string num;
int k, n;
int w[N];
int f[N][M];
void init() {
for (int j = 0; j < M; j++) {
for (int i = 1; i + (1 << j) - 1 <= n; i++) {
if (!j) f[i][j] = w[i];
else f[i][j] = min(f[i][j - 1], f[i + (1 << j - 1)][j - 1]);
}
}
}
int query(int l, int r) {
int len = r - l + 1;
int k = log(len) / log(2);
return min(f[l][k], f[r - (1 << k) + 1][k]);
}
int bsearch(PII q[], int k, int p) {
int l = 1, r = n;
while (l < r) {
int mid = l + r >> 1;
if (q[mid].first >= k) {
r = mid;
} else {
l = mid + 1;
}
}
int st = l;
r = n;
while (l < r) {
int mid = (l + r + 1) >> 1;
if (q[mid].first < k + 1) {
l = mid;
} else {
r = mid - 1;
}
}
int ed = l;
while (st < ed) {
int mid = st + ed >> 1;
if (q[mid].second >= p) {
ed = mid;
} else {
st = mid + 1;
}
}
return q[st].second;
}
int main() {
cin >> num;
cin >> k;
n = num.length();
int remain = n - k;
int p = 1, q = n - remain + 1;
for (int i = 1; i <= n; i++) {
vals[i] = {num[i - 1] - '0', i};
w[i] = num[i - 1] - '0';
}
sort(vals + 1, vals + n + 1);
init();
string res;
for(int i = 1; i <= remain; i++) {
int minval = query(p, q);
p = bsearch(vals, minval, p) + 1;
if (res.length() != 0 || minval != 0) {
res += minval + '0';
}
q ++;
}
if (res.length() == 0) {
res = "0";
}
cout << res << endl;
return 0;
}