[ABC378C] Repeating 题解

[ABC378C] Repeating 题解

解题思路

我们需要为每个 ​A_i 找到它在序列 ​A 中上一次出现的位置。你可能第一想法是使用桶来进行记录当前数在此之前的位置是什么。普通的桶在这一题显然是开不了的，因为数据量达到了 ​10^9。但其实使用map进行存储也同样可以通过本题。用map的思路比较好想，在这里重点讲一下通过排序实现本题的思路。

1. 数据结构选择

首先我们需要定义一个数据结构来存储每个元素的信息，包括该元素的值和它在原序列中的位置。我们可以使用一个结构体 node，其中 v 表示元素的值，p 表示元素的原始索引位置。

2. 排序

我们将所有的元素按照它们的值进行排序。排序后，相同的值会相邻排列。这样，我们只需要在相邻的元素中检查它们是否相同，如果相同，则说明它们是重复出现的，我们可以根据排序后的位置直接找到上一个出现的位置。

3. 填充结果

在遍历排序后的数组时，若当前元素的值和前一个元素相同，那么它的结果就是前一个元素的原始位置。否则，它的结果是 ​-1。

4. 时间复杂度

排序的时间复杂度是 ​O(N \log N)，然后遍历一次数组来填充结果是 ​O(N)。因此，总体时间复杂度是 ​O(N \log N)，这个题是完全可以pass的。

AC代码

#include<bits/stdc++.h>
#define ll long long
#define mem(x,y) memset(x,y,sizeof(x))
#define CLOSE ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
using namespace std;
const int inf=0x3f3f3f3f;
const int N=2e5+5;

int n, b[N];  // b数组用来存储结果
struct node {
    int p, v;  // p为元素在原数组中的位置，v为元素的值
} a[N];

bool cmp(node a, node b) {
    if(a.v == b.v) return a.p < b.p;  // 如果值相同，按位置排序
    return a.v < b.v;  // 如果值不同，按值排序
}

int main() {
    b[0] = -1;  // 初始化b数组的第一个值为-1，作为边界值
    cin >> n;  // 输入数组长度
    for(int i = 1; i <= n; i++) {
        cin >> a[i].v;  // 输入数组元素值
        a[i].p = i;  // 记录元素的原始位置
    }
  
    sort(a + 1, a + 1 + n, cmp);  // 按值排序

    // 填充b数组
    for(int i = 1; i <= n; i++) {
        if(a[i].v == a[i - 1].v) {
            b[a[i].p] = a[i - 1].p;  // 如果当前元素与前一个相同，则B[i]为前一个位置
        } else {
            b[a[i].p] = -1;  // 否则，B[i]为-1
        }
    }

    // 输出结果
    for(int i = 1; i <= n; i++) {
        cout << b[i] << " ";  // 输出每个B[i]值
    }

    return 0;
}