AcWing 244 迷一样的牛

题目传送门

算法分析

树状数组 + 二分

题目描述：给定\(n\)头牛，且\(h[i]\)表示第\(i\)头牛前面有\(h[i]\)头牛比它低，求每头牛的身高。

思路：需要从最后一头牛作为突破口，因为最后一头牛的\(h[n]\)表示，在前面的牛中，有\(h[n]\)头牛比它矮，即在所有的牛中，有\(h[n]\)头牛比他矮，因此最后一牛的高度在所有牛中排第\(h[n] + 1\)小。拿第\(n\)头牛作为信息点，去掉第\(n\)头牛，继续计算第\(n - 1\)头牛的高度，再去掉第\(n - 1\)头牛，依次类推… 当枚举到第\(i\)头牛时，在剩下的牛中高度中排第\(h[i] + 1\)小的高度，即是第\(i\)头牛的高度。

方法

方法1、可以使用两重循环枚举，先从后往前枚举每头牛，当枚举到第\(i\)头牛时，再从\(1\)枚举到\(n\)，找到第\(h[i] + 1\)个没有使用过的数，再对该数进行标记，继续枚举下一头牛，时间复杂度\(O(n^2)\)，超时
实现代码

#include 
using namespace std;
//通过了 7/10个数据
// https://www.bilibili.com/video/BV1Yb4y1s7Us/
const int N = 1e5 + 10;
int h[N];
int st[N];
int ans[N];
int n;
int main() {
    // https://www.acwing.com/solution/content/24500/
    cin >> n;
    /*
    举个栗子：
    5
    1 2 1 0

    注意~  这里只有三个数字，因为第一个0没有被输入，注意啊~

    答案：
    2 4 5 3 1

    正序遍历:
    0  1  2  1  0

    h3>h2>h4>h1>h5
    h5=1
    h4=3
    h3=5
    h2=4
    h1=2
    其它大佬留言：本题比较巧合，正着枚举可以形成n头牛之间的大小关系，不是例子序列的问题。
    就用例而言，是可以求出最终关系的，我也尝试通过构造的办法进行举反例，但没有成功，但想想就算是我能插入的办法写出
    暴力的办法，也没有更好的方法进行优化。

    倒序遍历：

    从后向前走可以直接确定下来当前奶牛的最终位置，而且，当它确定占据某个位置后，
    其它的奶牛要需要避让这个位置的，因为本来前面的奶牛就无法管着后面的，只能是后面的确定后，
    让前面的考虑避让。

    分析样例： st[i]用于记录第i个位置是否已经被某个奶牛占据掉，1表示可以用，0表示已占据

    倒着从头看,h[5]=0,表示前面没有比它矮的，它是最矮的，所以res[5]=1
    res[i]:0 0 0 0 1 st[i]:0 1 1 1 1

    倒数第二个，h[4]=1,表示4前面有1个比自己矮的,由于5占用了1号位置，所以这个4描述的事实就是，
    刚才5号奶牛占用了1号位置后，还存在1个奶牛比4号奶牛矮，所以res[4]=3
    res[i]:0 0 0 3 1 st[i]:0 1 0 1 1

    倒数第三个，h[3]=2，表示3前面有2个比自己矮的，所以res[3]=5
    res[i]:0 0 5 3 1 st[i]:0 1 0 1 0

    倒数第四个，h[2]=1,表示2前面有1个比自己矮的，所以res[1]=4
    res[i]:0 4 5 3 1 st[i]:0 1 0 0 0

    倒数第五个，h[1]=0,表示1前面没有自己自己矮的，所以res[1]=2
    res[i]:2 4 5 3 1 st[i]:0 0 0 0 0
    */
    for (int i = 1; i <= n; i++) st[i] = 1; //初始化st数组

    for (int i = 2; i <= n; ++i) cin >> h[i];
    for (int i = n; i >= 1; i--) { //从后向前枚举每头牛
        int cnt = 0;
        for (int j = 1; j <= n; j++) {
            if (st[j]) cnt++;
            if (cnt == h[i] + 1) { //寻找第h[i]+1个未被占据的位置
                st[j] = 0;         //标识此位置被某个奶牛占据过了
                ans[i] = j;        //记录i号奶牛占据的是j号位置
                break;
            }
        }
        cout << "ans[i]:";
        for (int i = 1; i <= n; i++) cout << ans[i] << " ";
        cout << "st[i]:";
        for (int i = 1; i <= n; i++) cout << st[i] << " ";
        cout << endl;
    }
    for (int i = 1; i <= n; i++) cout << ans[i] << endl;
    return 0;
}

方法2、树状数组 + 二分，从后往前枚举时，有两个操作
1、从剩余的数中找第\(k\)小的数
2、删除某个数

讲解视频
https://www.bilibili.com/video/BV1Yb4y1s7Us/

具体步骤

1、对于每头牛都初始化为\(1\)，\(a[i] = 1\),表示每头牛都未被使用，树状数组维护的是第\(i\)个高度中\(a[1] + a[2] + .. + a[i]\)的值，其中 \(a[i]\) 只有 \(0\) 和 \(1\) 两种情况。

2、在剩余的数中找第 \(k\) 小，即在所有满足 \(sum(x) = k\) 情况中，通过二分找到最小的 \(x\) ，如图所示

3、找到了当前牛的高度后删除该牛的高度，继续枚举
时间复杂度 \(O(nlogn)\)

实现代码

#include 
using namespace std;
const int N = 100010;
int a[N];
int ans[N];
int n;

// t[i]表示树状数组i结点覆盖的范围和
int t[N];

//返回非负整数x在二进制表示下最低位1及其后面的0构成的数值
int lowbit(int x) {
    return x & -x;
}
//将序列中第x个数加上k
void add(int x, int k) {
    for (int i = x; i <= n; i += lowbit(i)) t[i] += k;
}
//查询序列前x个数的和
int sum(int x) {
    int sum = 0;
    for (int i = x; i; i -= lowbit(i)) sum += t[i];
    return sum;
}

int main() {
    cin >> n;
    for (int i = 2; i <= n; i++) cin >> a[i]; //读入每头奶牛前面有几头奶牛比自己矮
    for (int i = 1; i <= n; i++) add(i, 1);   //利用树状数组，把1~n之间每个位置设置为1,方便后面用来求前缀和
    for (int i = n; i >= 1; i--) {
        //用二分找出前缀和恰好为a[i] + 1的数
        int l = 1, r = n;
        while (l < r) {
            int mid = l + r >> 1;
            if (sum(mid) >= a[i] + 1)
                r = mid; //再小点试试
            else
                l = mid + 1; //再大点~
        }
        ans[i] = l; //记录答案
        add(l, -1); //找到后，这个数-1,标识为0，方便下次求前缀和
    }
    //输出结果
    for (int i = 1; i <= n; i++) cout << ans[i] << endl;
    return 0;
}