Codeforces Round #555 (Div. 3)E. Minimum Array

6988 단어 CF이분
제목 링크
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;
}

좋은 웹페이지 즐겨찾기