算法提高课汇总

算法思路

考虑从左向右依次考虑每头牛的身高, 对于第一头牛, 在它之前比它低的🐂的个数
一定为$0$, 有效信息莫得.

而如果我们从右向左考虑, 对于最右侧牛有$A_n$头牛比它低, 也就是在所有🐂中,
最右侧牛第$A_{n+1}$低, 由于所有牛的高度为$1\sim n$的排列, 所以其高度就是$A_{n + 1}$.
在排列中去掉$A_{n+1}$后, 再次考虑当前最右侧牛$n - 1$, 同样的解题思路, 唯一区别
在于我们需要在剩余数字中找到第$A_{n-1}+1$小的数字.

题目要求两种操作:

• 在剩余排列中求第$k$小的数字.

• 删除某个数.

上述两个操作可以用平衡树实现, 但代码复杂度比较高. 考虑前缀和求解:
令$a_i = 1$表示数字$i$仍在排列中, $a_i = 0$表示其已被删除.

此时前缀和$sum(x) = k$表示在$1\sim x$中只有$k$个数可用. 若$a_x = 0$, 会出现$sum(x - 1) = sum(x)$的情况, 我们需要找到满足$sum(x) = k$的最小的$x$,
此时$1\sim x$中只有$k$个数可用, 且$a_x = 1$($x$可用) — $x$是剩余数字中第$k$小的数.
由于前缀和具有单调性,可以用二分优化.

而前缀和$sum(x)$的修改元素(令$a_i = 0$)以及前缀和的计算可以用树状数组维护
前缀和实现.

实现代码

#include <iostream>

using namespace std;

const int N = 1e5 + 10;

int n;
int a[N], ans[N];
int tr[N];

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

void add(int x, int c)
{
    for ( int i = x; i <= n; i += lowbit(i) )   tr[i] += c;
}

int sum(int x)
{
    int res = 0;
    for ( int i = x; i; i -= lowbit(i) )    res += tr[i];
    return res;
}

int main()
{
    cin >> n;
    for ( int i = 2; i <= n; i ++ ) cin >> a[i];

    //树状数组初始化 由于前缀和sum(x) = x
    //树状数组tr[x] = 区间长度lowbit(x)
    for ( int i = 1; i <= n; i ++ ) tr[i] = lowbit(i);

    for ( int i = n; i; i -- )
    {
        int k = a[i] + 1;
        int l = 1, r = n;
        while ( l < r )
        {
            int mid = l + r >> 1;
            if ( sum(mid) >= k )    r = mid;
            else    l = mid + 1;
        }
        ans[i] = l;
        add(l, -1);  //删除数字l 
    }

    for ( int i = 1; i <= n; i ++ ) cout << ans[i] << endl;

    return 0;
}