B. Modulo Equality-----사고/폭력

11563 단어 사유Codeforces
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
The third line contains n integers b1,b2,…,bn (0≤bi
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;
}

좋은 웹페이지 즐겨찾기