Codeforces Round #555 (Div. 3)E. Minimum Array
You are given two arrays a and b, both of length n. All elements of both arrays are from 0 to n−1.
You can reorder elements of the array b (if you want, you may leave the order of elements as it is). After that, let array c be the array of length n, the i-th element of this array is ci=(ai+bi)%n, where x%y is x modulo y.
Your task is to reorder elements of the array b to obtain the lexicographically minimum possible array c.
Array x of length n is lexicographically less than array y of length n, if there exists such i (1≤i≤n), that xi
Input The first line of the input contains one integer n (1≤n≤2⋅105) — the number of elements in a, b and c.
The second line of the input contains n integers a1,a2,…,an (0≤ai
The third line of the input contains n integers b1,b2,…,bn (0≤bi
Output Print the lexicographically minimum possible array c. Recall that your task is to reorder elements of the array b and obtain the lexicographically minimum possible array c, where the i-th element of c is ci=(ai+bi)%n.
Examples inputCopy 4 0 1 2 1 3 2 1 1 outputCopy 1 0 0 2 inputCopy 7 2 5 1 5 3 4 3 2 4 3 5 6 5 1 outputCopy 0 0 0 1 0 2 4
제목: 두 개의 길이가 n인 수조, 수조 a의 위치가 변하지 않으며, 수조 b의 위치를 바꾸고, 수조 cci=(ai+bi)%n을 구성하여 수조 c의 사전 서열을 최소화합니다.사고방식: 수조 c의 사전 서열을 최소화한다. 즉, 매번bi는ai+bi를 n보다 크고 n에 가깝게 하기 때문에 멀티셋으로 수조 b,lower 를 유지한다.bound(n-a[i])만 있으면 됩니다.
#include
using namespace std;
#define sc(x) scanf("%d",&x)
int a[210000],b[210000];
multiset<int>mu;
int main()
{
int n;
sc(n);
for(int i=0;i<n;i++) sc(a[i]);
for(int i=0;i<n;i++){int x;sc(x);mu.insert(x);};
multiset<int>::iterator it;
for(int i=0;i<n;i++){
it = mu.lower_bound(n-a[i]);
if(it == mu.end()) it = mu.begin();
cout<<(a[i]+*it)%n<<" ";
mu.erase(it);
}
cout<<endl;
return 0;
}
이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
1.11 프로그래밍 기초의 2분 찾기 04: 네트워크 담당자심판위원회는 인터넷 라인을 구매하기 위해 현지의 한 인터넷 솔루션 제공 업체에 연락하여 일정한 수량의 등장망 라인을 제공할 수 있도록 요구했다.심판위원회는 네트워크가 길어질수록 좋아져 선수들 사이의 거리가 가능한 한...
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.