牛牛的mex

牛牛的mex

https://ac.nowcoder.com/acm/contest/7079/A

图片说明

题目分析:题目说要求未出现的最小自然数,并且题目有条件,那就是元素值都小于n并且互不相等,那么我们可以维护一个前缀和最小值和一个后缀和最小值,最后未出现的最小自然数就在区间旁边取一个最小值就行。

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

const int maxn = 1e5 + 10;
int a[maxn], f[maxn], w[maxn];

int main()
{
    int l, r, n, q;
    scanf("%d%d", &n, &q);
    f[0] = w[n + 1] = n; //初始化
    for (int i = 1; i <= n; ++i)
        scanf("%d", &a[i]);
    for (int i = 1; i <= n; ++i) //维护一个前缀和最小值
        f[i] = min(f[i - 1], a[i]);
    for (int i = n; i >= 1; --i) //维护一个后缀和最小值
        w[i] = min(w[i + 1], a[i]);
    for (int i = 1; i <= q; ++i)
    {
        int l, r;
        scanf("%d%d", &l, &r);
        printf("%d\n", min(f[l - 1], w[r + 1])); //未出现的自然数最小值就在两边产生
    }
    return 0;
}
牛客比赛系列题解 文章被收录于专栏

加油加油

全部评论

相关推荐

2024-11-13 19:59
中南大学 自动化
Noob1024:一笔传三代,人走笔还在
点赞 评论 收藏
分享
评论
点赞
收藏
分享
牛客网
牛客企业服务