自动搬运

查看原文

来自洛谷，原作者为

	yzx3195 To my mediocre OI life.

搬运于2025-08-24 22:54:27，当前版本为作者最后更新于2024-01-21 16:10:09，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

题目描述

对于一个长度为 $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);
}