题解 CF1157E 【Minimum Array】

ModestCoder_ · 2019-08-28 11:39:09 · 题解

刚刚自己研究出了一个小技巧

对于每一个a_i，找n-a_i是否存在，不存在就找n-a_i+1,n-a_i+2...以此类推

想到用链表去实现一个查询的操作，但是一个一个找还是太慢，这让我想到了并查集

并查集的路径压缩的思路正好可以用在这里优化链表的查找

Code：

#include <bits/stdc++.h>
#define maxn 200010
using namespace std;
int n, a[maxn], cnt[maxn], nxt[maxn];

inline int read(){
    int s = 0, w = 1;
    char c = getchar();
    for (; !isdigit(c); c = getchar()) if (c == '-') w = -1;
    for (; isdigit(c); c = getchar()) s = (s << 1) + (s << 3) + (c ^ 48);
    return s * w;
}

int get(int x){ return cnt[x] ? x : nxt[x] = get(nxt[x]); }

int main(){
    n = read();
    for (int i = 1; i <= n; ++i) a[i] = read();
    for (int i = 1; i <= n; ++i){
        int x = read();
        ++cnt[x];
    }
    for (int i = 0; i < n; ++i) nxt[i] = i + 1; nxt[n] = 0;
    for (int i = 1; i <= n; ++i){
        int x = get(n - a[i]);
        --cnt[x]; printf("%d ", (a[i] + x) % n);
    }
    return 0;
}