题目链接:http://codeforces.com/contest/1130/problem/B
题意是输入一个n说明编号为1-n的蛋糕,然后输入2*n个数,表示编号为ai的蛋糕在第i个位置(1-n每个数出现两次),现在有两个人在第一个位置,他们两个人要分别要拿n个蛋糕,且只能按1-n的顺序拿蛋糕,每走一步的时间为1,问最少多长时间两个人能取完蛋糕。
思路是因为每个数一定出现两次,而且两个人都是按1-n的顺序拿蛋糕,所以我们编号为i的蛋糕,我们对两个人进行一个比较,使两个人都拿到第i个蛋糕的所用时间最小就好了,因为只有两种情况(a1拿b1,a2拿b2 或者 a1拿b2,a2拿b1)。具体实现方法就是将蛋糕和它的位置存起来,枚举第i号蛋糕,比较两种情况的最小值,然后更新两个人的位置就好了。
AC代码:
#include <bits/stdc++.h>
#define ll long long
using namespace std;
int n;
vector<int> v[100005];
int main()
{
scanf("%d",&n);
for(int i=1;i<=2*n;i++){
int x;
scanf("%d", &x);
v[x].push_back(i);
}
int t1 = 1, t2 = 1;
ll ans = 0;
for(int i=1;i<=n;i++){
int xx = abs(t1 - v[i][0]) + abs(t2 - v[i][1]);
int yy = abs(t1 - v[i][1]) + abs(t2 - v[i][0]);
ans += min(xx, yy);
t1 = v[i][0];
t2 = v[i][1];
}
printf("%lld\n", ans);
return 0;
}