夏日夜晚，小度看着庭院中长长的走廊，萌发出想要在上面散步的欲望，小度注意到月光透过树荫落在地砖上，并且由于树荫的遮蔽度不通，所以月光的亮度不同，为了直观地看到每个格子的亮度，小度用了一些自然数来表示它们的亮度。亮度越高则数字越大，亮度相同的数字相同。
走廊是只有一行地砖的直走廊。上面一共有 n 个格子，每个格子都被小度给予了一个数字 ai 来表示它的亮度。
小度现在站在 11 号格子，想要去到 n 号格子。小度可以正向或反向移动到相邻的格子，每次需要花费 11 的体力。
同时小度还有瞬移的能力，其可以花费 11 的体力来瞬移到与当前格子亮度相同的格子上。而且由于小度视野有限，只能瞬移到在当前格子后的第一次亮度相同的格子上。这也意味着不能反向瞬移。
小度想知道，到达 n 号格子需要花费的最小体力是多少。以此制定一个最优秀的散步方案。
格式
输入格式：
第一行一个整数 n ，表示走廊上一共有 n 个格子。 1≤n≤2∗10^5 , 0≤ai≤1∗10^6；
第二行 n 个整数，为自然数 ai 表示第 i 号格子的亮度。
#include<bits/stdc++.h> using namespace std; const int maxn=2e5+5; int n; int a[maxn]; int id[maxn]; int ne[maxn]; int d[maxn]; int bfs(int s){ queue<int> Q; Q.push(s); for(int i=0;i<n;i++){ d[i]=0x3fffffff; } d[s]=0; while(!Q.empty()){ int cur=Q.front();Q.pop(); if(cur==n-1) break; //往前走 if(cur-1>=0&&d[cur]+1<d[cur-1]){ Q.push(cur-1); d[cur-1]=d[cur]+1; } //往后走 if(cur-1<n&&d[cur]+1<d[cur+1]){ Q.push(cur+1); d[cur+1]=d[cur]+1; } //正向瞬移 if(ne[cur]!=0&&d[cur]+1<d[ne[cur]]){ Q.push(ne[cur]); d[ne[cur]]=d[cur]+1; } return d[n-1]; } } int main( ) { cin>>n; for(int i=0;i<n;i++){ cin>>a[i]; idx[i]=i; } //稳定排序，在数字相同的时候保持下标递增 stable_sort(idx,idx+n,[](int x,int y)){ return a[x]<a[y];} for(int i=0;i<n-1;i++){ if(a[idx[i]]==a[idx[i+1]]){ ne[idx[i]]=idx[i+1]; } } return 0; }
