题目描述

有 n 头奶牛，已知它们的身高为 1∼n 且各不相同，但不知道每头奶牛的具体身高。
现在这n头奶牛站成一列，已知第i头牛前面有Ai头牛比它低，求每头奶牛的身高。

输入格式

第1行：输入整数 n。
第2..n2..n行：每行输入一个整数 Ai，第 i行表示 i头牛前面有Ai 头牛比它低。
（注意：因为第 1 头牛前面没有牛，所以并没有将它列出）

输出格式

输出包含 n 行，每行输出一个整数表示牛的身高。
第i行输出第 i 头牛的身高。

样例

输入：5 1 2 1 0
输出：2 4 5 3 1

思路

单点更新 –> 树状数组
求前缀和大于等于Ai+1的第一个位置 –> 二分

java 代码

import java.util.Scanner;

public class Main {
    static Scanner scanner = new Scanner(System.in);

    static final int N = (int) 1e5 + 10;
    static int n = scanner.nextInt();

    // 输入的序列
    static int[] arr = new int[N];
    // 树状数组（维护前缀和）
    static int[] c = new int[N];
    // 每头🐂的身高
    static int[] ans = new int[N];

    static int lowbit(int x) {
        return x & (-x);
    }

    /**
     * 单点更新
     * @param x
     * @param t
     */
    public static void add(int x, int t) {
        for (int i = x; i <= n; i += lowbit(i)) {
            c[i] += t;
        }
    }

    /**
     * 区间查询
     * @param x
     */
    public static int query(int x) {
        int ans = 0;
        for (int i = x; i >= 1; i -= lowbit(i)) {
            ans += c[i];
        }
        return ans;
    }

    public static void main(String[] args) {
        for (int i = 2; i <= n; i++) {
            arr[i] = scanner.nextInt();
        }
        for (int i = 1; i <= n; i++) {
            // 初始化为1
            add(i, 1);
        }
        // 由后往前枚举
        for (int i = n; i >= 1; i--) {
            // 查找a[i]+1的位置
            int k = arr[i] + 1;
            // 二分
            int l = 1, r = n, mid;
            while (l < r) {
                mid = (l + r) / 2;
                if (query(mid) >= k) {
                    // 找大于等于k的最小值
                    r = mid;
                } else {
                    l = mid + 1;
                }
            }
            ans[i] = l;
            add(l,-1);
        }
        for (int i = 1; i <= n; i++) {
            System.out.println(ans[i]);
        }
    }
}