牛牛的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; }
牛客比赛系列题解 文章被收录于专栏
加油加油