[GDKOI2024 普及组] 读书 题解

· · 题解

题目描述

对于一个长度为 n 序列 A，若 A_i 之前未被取过，且在取出 A_i 前已取出的数的个数不小于 A_i，就可以把 A_i 取出，经过几次这样的取出操作，可以把序列取完。

做法

显然，有零取零，有较小的取较小的。

通过上面这句话，我们可以发现，现在问题似乎转化成了求一段区间内的最小值。这是什么？

线段树！

我们可以用一颗线段树去维护一个区间内的最小值，记为 tree，每次取数就把那个点赋为 \texttt {INF}，再记录一个 g，表示当前已经取了 g 个数，然后再看有没有节点小于 g，当 tree_1 为 \texttt {INF} 时，就退出，并输出 ans。

问题来了，如何判断无解呢？

读题可知，一本书最多只有 5 \times 10^5 章，在有解的情况下，我们每次都能读至少一章，至多也不会超过 5 \times 10^5 章，那么，我们可以记录一个 cnt，若 cnt 大于了 5 \times 10^5 则无解，输出 -1。

时间复杂度为 O(n \log n)。

Code

#include<bits/stdc++.h>
using namespace std;

const int MAXN = 5 * 1e05 + 7;

const int inf = 2147483647;

int n, d;

int a[MAXN];

int tree[MAXN * 4];

int g;

int cnt;

void Build(int l, int r, int p)
{
    if(l == r) 
    {
        tree[p] = a[l];
        return ;
    }
    int mid = (l + r) >> 1    ;
    Build(l, mid, p << 1);
    Build(mid + 1, r, p << 1 | 1);
    tree[p] = min(tree[p << 1], tree[p << 1 | 1]);
}

void Query(int p, int l, int r)
{
    if(l == r)
    {
        tree[p] = inf, ++g;
        return ;
    }
    int mid = (l + r) >> 1;
    if(tree[p << 1] <= g) Query(p << 1, l, mid);
    if(tree[p << 1 | 1] <= g) Query(p << 1 | 1, mid + 1, r);
    tree[p] = min(tree[p << 1], tree[p << 1 | 1]);
    return;
}

signed main()
{
//    freopen("book.in", "r", stdin);
//    freopen("book.out", "w", stdout);
    scanf("%d%d", &d, &n);

    for(int i = 1; i <= n; i++)
        scanf("%d", &a[i]);

    Build(1, n, 1);

    int ans = 0;    

    for(;;)
    {
        ans++;
        cnt++;
        Query(1, 1, n);
        if(tree[1] == inf) break;
        if(cnt >= MAXN)
        {
            printf("-1");
            return 0;
        }
    }

    printf("%d", ans);
}