假设车从点1向右(位置递增的方向)开出,行驶了$m$个站点后停止。记录每个位置的到达次数$c$。如果$b$与输入的询问序列中每个数字出现的次数$c$相同,则本次车程的距离珂以成为答案。
用两个指针$l$,$r$代表一次车程的起点和终点。每次计算完当前车程后,就将$l$,$r$各自往对应的方向挪一步并进行相关信息的更新。时间复杂度$O(N)$
```cpp
int n, m, a[N], cnt, b[N], c[N];
struct Pos
{
int p, d;
};
void move(Pos &p)
{
if (p.p == 1 && p.d == -1)
p.d = 1;
if (p.p == n && p.d == 1)
p.d = -1;
p.p += p.d;
}
int main()
{
ios::sync_with_stdio(false);
cin >> n;
ll cur = 0;
for (int i = 1; i <= n; i++)
cin >> a[i];
int t1;
cin >> m;
for (int i = 1; i <= m; i++)
cin >> t1, ++b[t1];
Pos l{1, 1}, r{1, 1};
++c[1];
for (int i = 1; i <= m - 1; i++)
{
int last = r.p;
move(r);
++c[r.p];
cur += abs(a[last] - a[r.p]);
}
for (int i = 1; i <= n; i++)
if (b[i] != c[i])
++cnt;
ll ans = -1;
for (int i = 1; i <= n * 2; i++)
{
if (!cnt)
{
if (ans == -1 || ans == cur)
ans = cur;
else
{
cout << -1 << endl;
return 0;
}
}
if (--c[l.p] == b[l.p])
--cnt;
else if (c[l.p] + 1 == b[l.p])
++cnt;
int ll = l.p, rr = r.p;
move(l);
move(r);
cur -= abs(a[l.p] - a[ll]);
cur += abs(a[r.p] - a[rr]);
if (++c[r.p] == b[r.p])
--cnt;
else if (c[r.p] - 1 == b[r.p])
++cnt;
}
cout << ans << endl;
return 0;
}
```