本文主要是介绍Codeforces Round #136 (Div. 1) C. Little Elephant and Shifts，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
题目链接：
http://codeforces.com/problemset/problem/220/C
C. Little Elephant and Shifts
The Little Elephant has two permutations a and b of length n, consisting of numbers from 1 to n, inclusive. Let's denote the i-th (1 ≤ i ≤ n) element of the permutation a as ai, the j-th (1 ≤ j ≤ n) element of the permutation b — as bj.
The distance between permutations a and b is the minimum absolute value of the difference between the positions of the occurrences of some number in a and in b. More formally, it's such minimum |i - j|, that ai = bj.
A cyclic shift number i (1 ≤ i ≤ n) of permutation b consisting from n elements is a permutation bibi + 1... bnb1b2... bi - 1. Overall a permutation has n cyclic shifts.
The Little Elephant wonders, for all cyclic shifts of permutation b, what is the distance between the cyclic shift and permutation a?
Input
The first line contains a single integer n (1 ≤ n ≤ 105) — the size of the permutations. The second line contains permutation a as ndistinct numbers from 1 to n, inclusive. The numbers are separated with single spaces. The third line contains permutation b in the same format.
Output
In n lines print n integers — the answers for cyclic shifts. Print the answers to the shifts in the order of the shifts' numeration in permutation b, that is, first for the 1-st cyclic shift, then for the 2-nd, and so on.
Examples
input
Copy
2 1 2 2 1output
Copy
1 0input
Copy
4 2 1 3 4 3 4 2 1output
Copy
2 1 0 1
题意：
给你一个a数组，一个b数组，都只含1-n，俩数组的距离定义为，if(a[i]==b[j])dis=min(dis,abs(j-i))，然后对于每一个b向左循环移动的排列，让你输出距离。分析：
若b[j]在a[i]的左边，随着每次左移，两点间dis+1
若b[j]在a[i]的右边，随着每次左移，两点间dis-1
每次的答案，从>=0的里面找最小的，<0的里面找最大的，两者再取最小对于如何模拟，举一个例子。
4
2 1 3 4
3 4 2 1
1. 将距离（b[i]-a[i])存入muliset里面：-2 -2 2 2我们知道要找绝对值最小值，即找最接近0的，然后即s.lower_bound(0) ans=min(0-(-2),2-0)
我们更新距离要这么更新，首先删除b首个元素的距离，把他放在最后。
a[]
2 1 3 4 移动后的b[] 4 2 1 3 multiset里面存的数据 -2 2 2 2 2.
muliset里面现在为：-2 2 2 2，找最小值的话，我们应该找最接近1的，因为对于两个数组，我们知道元素位置相差1才能是对应想等的
ans=min(1-(-2),2-1) ,因为我们在muliset实际情况没有减1，所以对于1左边的加一个1，1右边的减一个1.
其他步对应同理
This is the code：
#include<algorithm>
#include<cstdio>
#include<cstring>
#include<cmath>
#include<cstdlib>
#include<iostream>
#include<iomanip>
#include<list>
#include<map>
#include<queue>
#include<sstream>
#include<stack>
#include<string>
#include<set>
#include<vector>
using namespace std;
#define PI acos(-1.0)
#define pppp cout<<endl;
#define EPS 1e-8
#define LL long long
#define ULL unsigned long long //1844674407370955161
#define INT_INF 0x3f3f3f3f //1061109567
#define LL_INF 0x3f3f3f3f3f3f3f3f //4557430888798830399
// ios::sync_with_stdio(false);
// 那么cin, 就不能跟C的 scanf，sscanf, getchar, fgets之类的一起使用了。
const int dr[]={0, 0, -1, 1, -1, -1, 1, 1};
const int dc[]={-1, 1, 0, 0, -1, 1, -1, 1};
int read()//输入外挂
{int ret=0, flag=0;char ch;if((ch=getchar())=='-')flag=1;else if(ch>='0'&&ch<='9')ret = ch - '0';while((ch=getchar())>='0'&&ch<='9')ret=ret*10+(ch-'0');return flag ? -ret : ret;
}
const int maxn=100005;
int a[maxn];
int b[maxn];
multiset<int> ms;
multiset<int>::iterator msit;
int main()
{int n,x;scanf("%d",&n);for(int i=0; i<n; ++i)//注意循环对应{scanf("%d",&x);a[x]=i;}for(int i=0;i<n;++i)//注意和下边的那个循环对应起来{scanf("%d",&b[i]);ms.insert(i-a[b[i]]);//将b[j]和a[i]的距离存储起来，大于零表示b[j]在a[i]的右边,反之在左边}for(int i=0; i<n; ++i)//表示没有移动前差为多少，即表示时间戳，表示移动了几次{msit=ms.lower_bound(i);//找到正好差值为i的第一个int ans=INT_INF;if(msit!=ms.end())ans=min(ans,*msit-i);if(msit!=ms.begin())ans=min(ans,i-*(--msit));//找到差值的比i小的第一个printf("%d\n",ans);msit=ms.find(i-a[b[i]]); //找到当前最左边的那一个删除掉，然后添加在右边ms.erase(msit);ms.insert(i-a[b[i]]+n);//添加在右边相当于加了n}}
这篇关于Codeforces Round #136 (Div. 1) C. Little Elephant and Shifts的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
