讨厌鬼的数组构造

[题目链接](https://www.nowcoder.com/practice/883192b10c7a4527a469abe5967c7905)

思路

给定长度为 $n$ 的序列 $a$ ，要求构造一个长度为 $n$ 的序列 $b$ ，满足：

$1 \leq b_i \leq 10^9$
$(a_i + b_i) \bmod i = 0$ （ $i$ 从 $1$ 开始编号）
所有 $b_i$ 互不相同

确定候选值

对于位置 $i$ ，条件 $(a_i + b_i) \bmod i = 0$ 等价于 $b_i \equiv -a_i \pmod{i}$ 。

设 $r = i - (a_i \bmod i)$ ，若 $r = i$ 则令 $r = 0$ 。则 $b_i$ 的候选值为 $r, r+i, r+2i, \ldots$ 。由于 $b_i \geq 1$ ，当 $r = 0$ 时从 $i$ 开始取。

贪心策略

关键观察：编号越大的位置，步长越大，可选的值越稀疏。因此应该优先给大编号的位置分配值，再给小编号的位置分配——小编号位置步长小，候选值密集，容易找到未被占用的值。

具体做法：从 $i = n$ 到 $i = 1$ 倒序处理。对每个位置 $i$ ，从最小候选值开始，找到第一个未被使用的值，分配给 $b_i$ 并标记已用。

为什么一定能构造成功？

对于位置 $i$ ，候选值的间隔为 $i$ ，在 $[1, n \cdot n]$ 范围内至少有 $n$ 个候选值。而最多只有 $n - 1$ 个值已被占用，所以一定能找到可用的值。实际上由于我们优先处理大步长位置，冲突非常少，总查找次数近似 $O(n)$ 。

样例演示

$a = [3, 4, 7, 8, 10]$ ，从 $i = 5$ 开始：

$i$	$a_i$	$r = i - (a_i \bmod i)$	候选序列	选中
5	10	$5 - 0 = 5 \to r=0$ ，从 $5$ 起	5, 10, 15, ...	5
4	8	$4 - 0 = 4 \to r=0$ ，从 $4$ 起	4, 8, 12, ...	4
3	7	$3 - 1 = 2$	2, 5, 8, ...	2
2	4	$2 - 0 = 2 \to r=0$ ，从 $2$ 起	2, 4, 6, ...	6
1	3	$1 - 0 = 1 \to r=0$ ，从 $1$ 起	1, 2, 3, ...	1

输出 $b = [1, 6, 2, 4, 5]$ ，验证每个位置 $(a_i + b_i) \bmod i = 0$ 均成立。

代码

C++
Java
Python3
JavaScript

#include <bits/stdc++.h>
using namespace std;

int main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n;
    cin >> n;
    vector<int> a(n+1);
    for(int i = 1; i <= n; i++) cin >> a[i];

    vector<long long> b(n+1, 0);
    set<long long> used;

    for(int i = n; i >= 1; i--){
        long long r = (long long)i - (a[i] % i);
        if(r == i) r = 0;
        long long start = (r == 0) ? i : r;
        for(long long v = start; ; v += i){
            if(used.find(v) == used.end()){
                b[i] = v;
                used.insert(v);
                break;
            }
        }
    }

    for(int i = 1; i <= n; i++){
        cout << b[i];
        if(i < n) cout << ' ';
    }
    cout << '\n';
    return 0;
}

import java.util.*;
import java.io.*;

public class Main {
    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(br.readLine().trim());
        StringTokenizer st = new StringTokenizer(br.readLine().trim());
        int[] a = new int[n + 1];
        for (int i = 1; i <= n; i++) a[i] = Integer.parseInt(st.nextToken());

        long[] b = new long[n + 1];
        Set<Long> used = new HashSet<>();

        for (int i = n; i >= 1; i--) {
            long r = (long) i - (a[i] % i);
            if (r == i) r = 0;
            long start = (r == 0) ? i : r;
            for (long v = start; ; v += i) {
                if (!used.contains(v)) {
                    b[i] = v;
                    used.add(v);
                    break;
                }
            }
        }

        StringBuilder sb = new StringBuilder();
        for (int i = 1; i <= n; i++) {
            if (i > 1) sb.append(' ');
            sb.append(b[i]);
        }
        System.out.println(sb);
    }
}

import sys
input = sys.stdin.readline

def main():
    n = int(input())
    a = [0] + list(map(int, input().split()))

    b = [0] * (n + 1)
    used = set()

    for i in range(n, 0, -1):
        r = i - (a[i] % i)
        if r == i:
            r = 0
        start = i if r == 0 else r
        v = start
        while v in used:
            v += i
        b[i] = v
        used.add(v)

    print(' '.join(str(b[i]) for i in range(1, n + 1)))

main()

const readline = require('readline');
const rl = readline.createInterface({ input: process.stdin });
const lines = [];
rl.on('line', line => lines.push(line.trim()));
rl.on('close', () => {
    const n = parseInt(lines[0]);
    const a = [0, ...lines[1].split(' ').map(Number)];

    const b = new Array(n + 1).fill(0);
    const used = new Set();

    for (let i = n; i >= 1; i--) {
        let r = i - (a[i] % i);
        if (r === i) r = 0;
        let start = r === 0 ? i : r;
        let v = start;
        while (used.has(v)) v += i;
        b[i] = v;
        used.add(v);
    }

    const res = [];
    for (let i = 1; i <= n; i++) res.push(b[i]);
    console.log(res.join(' '));
});

复杂度分析

时间复杂度： $O(n \log n)$ 。每个位置平均只需尝试常数次候选值（冲突极少），每次 set 操作 $O(\log n)$ 。
空间复杂度： $O(n)$ 。存储数组 $b$ 和已用值集合。