杂题——夏日漫步

夏日漫步

原题

夏日夜晚，小度看着庭院中长长的走廊，萌发出想要在上面散步的欲望，小度注意到月光透过树荫落在地砖上，并且由于树荫的遮蔽度不通，所以月光的亮度不同，为了直观地看到每个格子的亮度，小度用了一些自然数来表示它们的亮度。亮度越高则数字越大，亮度相同的数字相同。

走廊是只有一行地砖的直走廊。上面一共有 n 个格子，每个格子都被小度给予了一个数字 a i 来表示它的亮度。

小度现在站在 1 号格子，想要去到 n 号格子。小度可以正向或反向移动到相邻的格子，每次需要花费 1 的体力。

同时小度还有瞬移的能力，其可以花费 1 的体力来瞬移到与当前格子亮度相同的格子上。而且由于小度视野有限，只能瞬移到在当前格子后的第一次亮度相同的格子上。这也意味着不能反向瞬移。

小度想知道，到达 n 号格子需要花费的最小体力是多少。以此制定一个最优秀的散步方案。

格式

输入格式：

第一行一个整数 n ，表示走廊上一共有 n 个格子。 1≤n≤2∗105 ,0≤a i≤1∗106；
第二行 n 个整数，为自然数 a i​ 表示第 i 号格子的亮度。

输出格式：

一行，一个整数cost表示花费的最小体力。

样例 1

输入：

1
2
6
0 1 2 3 1 5

复制

输出：

1
3

思路

​ 这道题目一般我们乍眼一看就知道是一道简单的BFS类型题目，然后我们在处理瞬移操作的时候我们就会发现，如果我们通过枚举的方式来寻找相同值这种方式是铁TLE的，因此我们要想一想如何快速搜索一个数的下一个与之相同的数的位置，我们也可以很快想到使用数组在存储，这里我使用的ne[i]数组，表示位置i之后对应与之第一次相同的数值的下标位置，如果不存在的话就是0。

​ 难点就来了，怎么实现这种关系呢？一开始的思路是使用sort，sort(idx + 1, idx + n + 1, [](int x,int y){return a[x] < a[y];}); 这样就可以实现将对应下标按照a[i]的大小来排序形成的下标，这样的话就可以将相同数值的下标放在一堆了，但是问题又来了。第一发就出现了18/50的情况，然后发现是因为可能在排序的过程中会出现下标位置的错乱，比如说原来相对应的相同数值的下标为2，4，5，但是排序之后变为4，2，5。这里在网上找到这样一个sort函数stable_sort ，它和sort就只有一个区别：对于[first, last)范围内值相同的元素，该函数不会改变它们的相对位置。

代码

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
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
#include<bits/stdc++.h> 

using namespace std;
const int N = 2e5 + 10;
int n;
int a[N];
int idx[N];
int ne[N];
int d[N];

void bfs() {
    memset(d, 0x3f, sizeof d);
    queue<int> q;
    q.push(1);
    d[1] = 0;

    while (q.size()) {
        int t = q.front();
        q.pop();
        if (t == n) break;
        if (t - 1 >= 1 && d[t] + 1 < d[t - 1]) {
            q.push(t - 1);
            d[t - 1] = d[t] + 1;
        }

        if (t + 1 <= n && d[t] + 1 < d[t + 1]) {
            q.push(t + 1);
            d[t + 1] = d[t] + 1;
        }

        if (ne[t] != 0 && d[t] + 1 < d[ne[t]]) {
            q.push(ne[t]);
            d[ne[t]] = d[t] + 1;
        }
    }
}

int main( )
{
    ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
    cin >> n;
    for (int i = 1; i <= n; i++){
        cin >> a[i];
        idx[i] = i;
    }
	// 这道题目的精华，如何实现存储每个位置的下一个与之对应的相同的值
    stable_sort(idx + 1, idx + n + 1, [](int x,int y){return a[x] < a[y];});
	
    for (int i = 1; i < n; i++){
        if (a[idx[i]] == a[idx[i + 1]]) {
            ne[idx[i]] = idx[i + 1];
        }
    }

    bfs();

    cout << d[n];
    return 0;
}