小R与群山

Posted on Edited on In

题目大意：一个n位数，删除其中k个数字，使得留下的数字最小，问最小是多少其中n属于1e6，k属于n

我们可以显然的证明这样的贪心是错误的：删掉其中前k大的数字

做法很多，给出一种简单，易证的做法：

首先要求最小，显然是希望首位尽可能小，因为199…要比919…优秀

所以我们可以从第一位开始枚举，维护一个单调递增的栈，一旦发现某一位置小于栈顶，就不断弹

因为是递增的，所以首位一定是尽可能的小，这就满足了贪心的正确性

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
#include <bits/stdc++.h>
#define ll long long
using namespace std;

const int N = 1e6 + 66;

int n, k, top;
int a[N], sta[N], vis[N];
char ch[N];

signed main()
{
    int i;
    scanf ("%s", ch + 1), k = read(), n = strlen(ch + 1);
    if (n == k) {puts("0"); return 0;}
    for (i = 1; i <= n; ++ i) a[i] = ch[i] - '0', vis[i] = 1;

    sta[++ top] = 1;
    for (i = 2; i <= n; ++ i)
    {
        if (a[i] > a[sta[top]]) sta[++ top] = i;
        else
        {
            while (a[i] < a[sta[top]])
            {
                vis[sta[top]] = 0, top --;
                if (! (-- k)) break;
            }
            sta[++ top] = i;
        }
        if (k == 0) break;
    }
    
    if (k) for (i = n; i >= 1; -- i) if (vis[i]) {vis[i] = 0; if (! (-- k)) break;}
    
    memset(a, 0, sizeof a), top = 0;
    for (i = 1; i <= n; ++ i) if (vis[i]) a[++ top] = ch[i] - '0';
    int now = 1;
    while (a[now] == 0 && now < top) ++ now;
    for (i = now; i <= top; ++ i) cout << a[i];
    puts("");

    fclose(stdin), fclose(stdout);
    return 0;
}

总结：

期望得分：100+？+50pts

实际得分：100+22+50pts

考场上灵感突然就来了，一眼切，但是debug，写对拍，总共花了55分钟，一道水题浪费这么多时间，实属不应该，但是同机房dalao有人用单调队列切了有人用线段树码了一百多行切了%%%

第二题是个很简单的最小生成树的问题，但是考场脑子过于紧张，一直在思考最短路，没反应过来是个生成树

第三题神仙题，会搜索加上换根dp50分暴力，正解是换根dp