黑龙江农垦科技职业学院喜迎寒假多校联赛2(快乐ak场)E题题解

题目链接: 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;
}

上一篇:第三章 最简单的C程序设计--顺序程序设计


下一篇:C++快读快写(适用于整数变量)模版(详细注释版)