B. Modulo Equality-----사고/폭력
11563 단어 사유Codeforces
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;
}
이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
codeforce 991E(조합수 반복 검색)제목 링크: 링크 열기 클릭 샤오밍이 헷갈릴 때 본 자동차 번호판 숫자를 실제 숫자와 비교해 보자. ① 실제로 나온 숫자는 샤오밍이 다 봤다 ② 샤오밍은 같은 숫자만 보고 적을 수는 없다 ③ 차량 번호는 전도 제로가...
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.