题目链接: https://ac.nowcoder.com/acm/contest/11471/E
题目描述
这一天Kadia与Majiagou在教学弟,
突然提出了一个问题 给你一个超大的数字 让你从中删掉几位 怎么让他最小?
这种签到题不会还有人写不出来吧 不会吧不会吧
输入描述:
第一行输入一个整数N 1<=len(N)<=2×107 第二行输入一个整数k代表删除几个数字 0<=k<=len(N)
输出描述:
输出结果
示例1
输入:
10000 1
输出:
0
说明:
删掉1结果为0
示例2
输入:
12347897187194164979 10
输出:
1114164979
题解
此题思路很简单,很容易想到一下思路
N中去掉k位使其最小,可以逆向理解为,N中取|N|-k位使其最小,由贪心可知,高位越小,那么结果越小,因为可以优先使第一位最小,然后再此基础上使后面几位最小,而后面几位最小和第一位最小是一样的问题,这样就将整体最优解分解为局部最优解了。
然而确定了这个思路后菜菜的我却TLE了N多发,优化了好久,自己写快读,剪枝,读的时候就存储字符串长度,O2优化等,但是忽略了一个重要的一点,如果选中了0那么没必要继续遍历下去,直接得到结果了,我怀疑我就是卡到了这样的又长又很多0的测试了。。。
第二种思路就是维护单调栈,但是单调栈得略加修改,因为长度必须要是|N|-k。
以下是第一种思路的实现源码。
#pragma GCC optimize(2)
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
const int mod = 1e9 + 7;
const int inf = 0x3f3f3f3f;
template<typename T> void read(T& res) {
T x = 0, f = 0;
char ch = getchar();
while (!isdigit(ch)) { f |= ch == '-', ch = getchar(); }
while (isdigit(ch)) { x = 10 * x + ch - '0', ch = getchar(); }
res = f ? -x : x;
}
template<typename T> void print(T x) {
if (x < 0) { putchar('-'), x = -x; }
if (x >= 10) { print(x / 10); }
putchar(x % 10 + '0');
}
template<typename T> void print(T x, char let) {
print(x), putchar(let);
}
inline int read(char * str, char let = '\n') {
char ch = '\0';
int i = 0;
while ((ch = getchar()) != let) {
str[i++] = ch;
}
str[i] = '\0';
return i;
}
inline void print_s(const char *str) {
for(int i = 0;str[i] != '\0';++i) {
putchar(str[i]);
}
}
const int maxn = 2e7+20;
char pre[maxn];
int k;
char res[maxn];
int n;
int now = 0;
void dfs(int id, int l, int r) {
if(id == n - k) {
return;
}
int flag = l;
if(l == r) {
for(int i = l;i < n;++i) {
if(!(now == 0 && pre[i] == '0')) {
res[now++] = pre[i];
}
}
return;
}
for(int i = l;i <= r && pre[flag] != '0';++i) {
if(pre[flag] > pre[i]) {
flag = i;
}
}
if(!(now == 0 && pre[flag] == '0')) {
res[now++] = pre[flag];
}
dfs(id + 1, flag + 1, r + 1);
}
int main() {
n = read(pre);
read(k);
if(n == k) {
putchar('\n');
return 0;
}
dfs(0, 0, k);
res[now] = '\0';
if(now == 0) {
putchar('0');
putchar('\n');
} else {
print_s(res);
}
return 0;
}