pyy整队

Posted on Edited on In

题目大意：pyy让班里n个同学先排好队。站在队伍前端玩手机，前面的人少了，谁都顶不住。于是陆陆续续有人往队伍最后躲去，但大家都忘记了老师说前面位置有空缺要补齐的要求。一些同学还时不时地低头问向指挥队伍的班长pyy，排在自己前面成绩最好的同学是谁。这时老师来了，看着到处充满空缺的队伍，老师限pyy以最快的时间整顿队伍。体育老师看不出来队伍的位置后移了，老师只关心队伍是否整齐没有空缺。老师给了pyy一次移动一名同学的权力，因此pyy无法使用技能“向前看齐”。问你至少移动多少个同学可以使队伍整齐。

首先看见这个排名这么大，肯定要离散化一下，然后要求查询最小值，构造一个权值线段树就可以了，对于最后的移动同学，我们尝试维护一个长度为n 的滑动窗口，维护零的个数，然后就没了

对于往后挪动的同学，我们令他们的排名为++n就好了

注意：开ll！且在opt之后的那个数字也要开ll

代码如下：

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
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
#include <bits/stdc++.h>
#define int long long
using namespace std;

const int N = 2e5 + 666, inf = 214748360000;

int n, m, num, res = inf;
int a[N], b[N], pos[N], vis[N];

struct SEGMENTTREE
{
    int minv;
}tree[N << 2];

inline void up(int p)
{
    int l = p << 1, r = (p << 1) | 1;
    return (void)(tree[p].minv = min(tree[l].minv, tree[r].minv));
}

inline void build(int p, int l, int r)
{
    if (l == r) return (void)(tree[p].minv = pos[l]);
    int mid = (l + r) >> 1;
    build(p << 1, l, mid), build((p << 1) | 1, mid + 1, r);
    return (void)(up(p));
}

inline void updata(int p, int l, int r, int k, int val)
{
    if (l == r) return (void)(tree[p].minv = val);
    int mid = (l + r) >> 1;
    if (k <= mid) updata(p << 1, l, mid, k, val);
    if (k > mid) updata((p << 1) | 1, mid + 1, r, k, val);
    return (void)(up(p));
}

inline int query(int p, int l, int r, int k)
{
    if (l == r) return l;
    int mid = (l + r) >> 1;
    if (tree[p << 1].minv < k) return query(p << 1, l, mid, k);
    return query((p << 1) | 1, mid + 1, r, k);
}

signed main()
{	
    int i;
    n = read(), m = read(), num = n;
    for (i = 1; i <= n; ++ i)
    {
        a[i] = read();
        b[i] = a[i];
    }
    sort(b + 1, b + n + 1);
    for (i = 1; i <= n; ++ i)
    {
        a[i] = lower_bound(b + 1, b + n + 1, a[i]) - b;
        pos[a[i]] = i;
    }
    build(1, 1, 1e5);

    for (i = 1; i <= m; ++ i)
    {
        char opt[66]; int x;
        scanf ("%s%lld", opt, &x);
        x = lower_bound(b + 1, b + n + 1, x) - b;
        if (opt[0] == 'A')
        {
            int y = query(1, 1, 1e5, pos[x]);
            if (b[y] == 0) put(-1);
            else put(b[y]);
        }
        else
        {
            pos[x] = num + 1;
            ++ num;
            updata(1, 1, 1e5, x, pos[x]);
        }
    }
    for (i = 1; i <= n; ++ i) vis[pos[a[i]]] = 1;

    int ret = 0;
    for (i = 1; i <= 2e5; ++ i)
    {
        if (! vis[i]) ++ ret;
        if (i > n) 
            if (! vis[i - n])
                -- ret;
        if (i >= n) res = min(res, ret);
    }
    put(res);
    return 0;
}

总结：配上放爆竹那个题目，我期望得分是100+30pts，实际上是20+0pts，我第三题的思路其实是没有问题的，没时间来写了。

我发誓不做平庸的人！