1.4 找不同

发表于 | 更新于 | 分类于 | 阅读次数：

实验任务

对于一个数组，可以玩很多次找不同；每次提问会给出一个位置范围\([L,R]\)及一个数 \(x\)，你要做的是：在数组的第 \(L\) 个数到第 \(R\) 个数中，找出第一个不是 \(x\)的数所在的位置（即它在整个数组中是第几个数）。

数据输入

输入第一行为两个正整数 n,q，表示数组长度及“找不同” 的次数。接下去一行 n 个正整数，表示数组，以空格隔开。接下去 q 行，每行三个正整数 L,R,x,表示一次提问。

数据输出

依次对每个提问输出答案。如果没有满足条件的数，输出” -1” 。

输入示例 输出示例
6 4
1 2 1 1 3 5
1 4 1
2 6 2
3 4 1
3 4 2		 2
3
-1
3

数据范围

数组中的元素及每次询问的 \(x\leq 10^9\)；\(1\leq L\leq R\leq n\)；\(80\%\)的得分点，\(n, q\leq 1000\)；其余 \(20\%\)的得分点，\(n, q\leq 200000\)。

源代码

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
#include <iostream>
using namespace std;
#define maxn 200005

class Difference{
public:
    int data;
    int next;
    Difference() :data(0), next(-1) {}
};

Difference dif[maxn];

//预处理：连接相邻相同区间，如此查找复杂度降为O(1)
int main(){
    int n, q, i;
    scanf("%d%d", &n, &q);
    for (i = 1; i <= n; ++i)
        scanf("%d", &dif[i].data);
    for (i = n - 1; i > 0; --i)
        dif[i].next = dif[i].data != dif[i + 1].data ? i + 1 : dif[i + 1].next;
    int L, R, x;
    for (i = 0; i < q; ++i){
        scanf("%d%d%d", &L, &R, &x);
        if (dif[L].data != x)
            printf("%d\n", L);
        else
            printf("%d\n", dif[L].next <= R ? dif[L].next : -1);
    }
    return 0;
}

设计思路与复杂度分析

如果枚举\(L\rightarrow R\)，最坏情况需要遍历整个数组，然后发现找不到解，复杂度为\(O(n\times q)\)。 最坏情况下，因为相同的值导致需要遍历很多不需要的位置，那么就可以合并位置相邻且数值相同的数为一个数段。这样，如果位置\(L\)的值不是\(x\)，则答案就是\(L\)，否则答案为下一个数段的起始位置。如果下一个数段超出询问区间则返回\(-1\)。这样预处理之后，查找复杂度降为\(O(1)\)，整体复杂度降为\(O(\max(n,q))\)。

0%