BD202311 夏日漫步
作者:
Jiarui1111
,
2023-09-12 18:18:13
,
所有人可见
,
阅读 245
#include <bits/stdc++.h>
using namespace std;
#define int long long
constexpr int N = 200010, M = 1000010;
constexpr int inf = 1E18, mod = 1000000007;
int n, a[N], cost[N];
bool vis[N];
vector<int> G[M];
inline void BFS() {
queue<int> q;
q.push(1);
vis[1] = true;
while(q.size()) {
int u = q.front();
q.pop();
if(G[a[u]].size() >= 1) {
int t = lower_bound(G[a[u]].begin(), G[a[u]].end(), u) - G[a[u]].begin();
if(t < G[a[u]].size() - 1 && !vis[G[a[u]][t + 1]]) {
vis[G[a[u]][t + 1]] = true;
cost[G[a[u]][t + 1]] = cost[u] + 1;
q.push(G[a[u]][t + 1]);
}
}
if(u + 1 <= n && !vis[u + 1]) {
cost[u + 1] = cost[u] + 1;
vis[u + 1] = true;
q.push(u + 1);
}
if(u - 1 >= 1 && !vis[u - 1]) {
cost[u - 1] = cost[u] + 1;
vis[u - 1] = true;
q.push(u - 1);
}
}
}
inline void Main() {
cin >> n;
for (int i = 1; i <= n; i ++) {
cin >> a[i];
G[a[i]].push_back(i);
}
BFS();
cout << cost[n] << '\n';
}
signed main() {
cin.tie(nullptr)->sync_with_stdio(false);
int T = 1;
while(T --) Main();
return 0;
}