You are given a positive integer m and two integer sequence: a=[a1,a2,…,an] and b=[b1,b2,…,bn]. Both of these sequence have a length n.
Permutation is a sequence of n different positive integers from 1 to n. For example, these sequences are permutations: [1], [1,2], [2,1], [6,7,3,4,1,2,5]. These are not: [0], [1,1], [2,3].
You need to find the non-negative integer x, and increase all elements of ai by x, modulo m (i.e. you want to change ai to (ai+x)modm), so it would be possible to rearrange elements of a to make it equal b, among them you need to find the smallest possible x.
In other words, you need to find the smallest non-negative integer x, for which it is possible to find some permutation p=[p1,p2,…,pn], such that for all 1≤i≤n, (ai+x)modm=bpi, where ymodm — remainder of division of y by m.
For example, if m=3, a=[0,0,2,1],b=[2,0,1,1], you can choose x=1, and a will be equal to [1,1,0,2] and you can rearrange it to make it equal [2,0,1,1], which is equal to b.
Input
The first line contains two integers n,m (1≤n≤2000,1≤m≤109): number of elemens in arrays and m.
The second line contains n integers a1,a2,…,an (0≤ai<m).
The third line contains n integers b1,b2,…,bn (0≤bi<m).
It is guaranteed that there exists some non-negative integer x, such that it would be possible to find some permutation p1,p2,…,pn such that (ai+x)modm=bpi.
Output
Print one integer, the smallest non-negative integer x, such that it would be possible to find some permutation p1,p2,…,pn such that (ai+x)modm=bpi for all 1≤i≤n.
Examples
inputCopy
4 3
0 0 2 1
2 0 1 1
outputCopy
1
inputCopy
3 2
0 0 0
1 1 1
outputCopy
1
inputCopy
5 10
0 0 0 1 2
2 1 0 0 0
outputCopy
0
题意:给定一个a序列，b序列，找出一个x，使得(ai+x)%m=bpi(pi在这里作为下标)
实际p也是一个序列。请问x最小为多少。
解析:给a序列,b序列排序。先遍历一遍看是不是初始就是相同的，若是输出0，若不是继续。我们可以枚举a序列作为起点，和b[0]作比较，得出x(为什么只和b[0]做比较呢，因为枚举a序列，最终肯定有一个数通过公式得到b[0]，那么这个数肯定是我们的答案)。每次得到x后会得到一个新的序列，然后排序。我们和b序列去比较若相同ans=min(ans,x)直到答案最优
时间复杂度:O(n^2log(n))
#include<bits/stdc++.h>
using namespace std;
const int N=1e5+1000;
int a[N],b[N],c[N];
int n,m;
int main()
{
cin>>n>>m;
for(int i=1;i<=n;i++) cin>>a[i];
for(int i=1;i<=n;i++) cin>>b[i];
sort(a+1,a+1+n);sort(b+1,b+1+n);
int f=1;
for(int i=1;i<=n;i++)
{
if(a[i]!=b[i])
{
f=0;
break;
}
}
if(f==1)
{
cout<<0<<endl;
return 0;
}
int ans=0x3f3f3f3f;
for(int i=1;i<=n;i++)
{
int x=b[1]>a[i] ? b[1]-a[i] :b[1]+m-a[i];
for(int j=1;j<=n;j++) c[j]=(a[j]+x)%m;
sort(c+1,c+1+n);
int flag=0;
for(int j=1;j<=n;j++)
{
if(b[j]!=c[j])
{
flag=1;
break;
}
}
if(flag==0) ans=min(ans,x);
}
cout<<ans<<endl;
}