HDU3183《A Magic Lamp》

八月 08, 2019 2938

Description

Kiki likes traveling. One day she finds a magic lamp, unfortunately the genie in the lamp is not so kind. Kiki must answer a question, and then the genie will realize one of her dreams.

The question is: give you an integer, you are allowed to delete exactly m digits. The left digits will form a new integer. You should make it minimum.
You are not allowed to change the order of the digits. Now can you help Kiki to realize her dream?

Input

There are several test cases.
Each test case will contain an integer you are given (which may at most contains 1000 digits.) and the integer m (if the integer contains n digits, m will not bigger then n). The given integer will not contain leading zero.

Output

For each case, output the minimum result you can get in one line.
If the result contains leading zero, ignore it.

Sample Input

1
2
3
4
5
178543 4 
1000001 1
100001 2
12345 2
54321 2

Sample Output

1
2
3
4
5
13
1
0
123
321

解析

显然删除从左向右遇到的第一个比下一个数大的数，也就是让最高位最小的过程。那么按这样的策略做 m 次即可获得正确答案，删除后的序列可使用双向链表（STL 里有std::list<int>）来维护。

代码实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
//
//  HDU3183.cpp
//  Title: A Magic Lamp
//  Debugging
//
//  Created by HandwerSTD on 2019/8/8.
//  Copyright © 2019 HandwerSTD. All rights reserved.
//

#include <algorithm>
#include <iostream>
#include <cstring>
#include <cstdio>
#include <vector>
#include <list>

#define FILE_IN(__fname) freopen(__fname, "r", stdin)
#define FILE_OUT(__fname) freopen(__fname, "w", stdout)
#define rap(a,s,t,i) for (int a = s; a <= t; a += i)
#define basketball(a,t,s,i) for (int a = t; a > s; a -= i)
#define countdown(s) while (s --> 0)
#define IMPROVE_IO() std::ios::sync_with_stdio(false)
#define charat(x) ((x - 1))

using std::cin;
using std::cout;
using std::endl;

typedef long long int lli;

int getint() { int x; scanf("%d", &x); return x; }
lli getll() { long long int x; scanf("%lld", &x); return x; }

/**
 * 删除从左向右遇到的第一个比下一个数大的数
 * 用一个双向链表维护
 */

int m;
std::string s;
std::list<int> lst;

int main() {
    while (cin >> s >> m) {
        int n = (int) s.length();
        lst.clear();
        for (int i = 1; i <= n; ++i) {
            lst.insert(lst.end(), s[charat(i)] - '0');
        }
        for (int i = 1; i <= m; ++i) {
            for (auto i = lst.begin(); i != lst.end(); i++) {
                i++; if (i == lst.end()) { --i; lst.erase(i); break; }
                int next = (*i);
                --i;
                if (*i > next) { lst.erase(i); break; }
            }
        }
        bool fz = true;
        for (auto i : lst) { if (fz && i == 0) continue; fz = false; printf("%d", i); }
        if (fz) printf("0");
        puts("");
    }
    return 0;
}