python/TangDou/AcWing/BIT/244.md

##AcWing 244 迷一样的牛

一、题目描述

有 n 头奶牛，已知它们的身高为 1∼n 且 各不相同，但不知道每头奶牛的具体身高。

现在这 n 头奶牛站成一列，已知第 i 头牛前面有 A_i头牛比它低，求每头奶牛的身高。

输入格式

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

输出格式

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

第 i 行输出第 i 头牛的身高。

数据范围 1≤n≤10^5

二、解题方法

这个题意不太好理解，我尝试理解一下： 每头牛都只关心 自己前面比自己短的牛个数 最直观的办法是看测试样例：

//输入样例
5
1
2
1
0
//输出样例
2
4
5
3
1

5头牛，第一头牛没有前面的其它牛，没有给出它前面有多少头牛比自己低，有数字也只能是0，题目就没有给出，所以我们看到的1,2,1,0是从第二头牛开发的。

	第二头牛	第三头牛	第四头牛	第五头牛
向前看	1	2	1	0

我认为，凡是这类一开始时，所求答案完全未知的问题，应该在 边界问题 上寻找原问题的 突破口 。因为对于那些靠近问题空间 中部 的子问题，其 左右两边 可以认为和它是本质相同的子问题，没有办法直接解决。因此我们应该 着重 考虑边界处的子问题。

这东西 不能从前向后去尝试，原因很简单，比如以第三头牛为例，它知道自己前面有2个比自己小的,但是不知道自己后面有几个比自己小的，也就不知道自己在整体中是第几，确定不下来。

这东西 可以从右向前去尝试，为啥呢？

在本题中，我们 首先考虑最后一头牛。由于它已经统计了在它之前的所有牛，因此，假如它比x头牛高，则它的高度一定是x+1。

我们 采取从后往前考虑的方式，就是因为题目给出了 每头牛已知在自己前面比自己矮的牛的个数 这一条件，从后往前可以少考虑很多问题。

由于每头牛的高度各不相同 且取遍区间[1,n]，因此，对于倒数第二头牛而言，它应该在除去上述x+1的区间[1,n]中，选取h_{i}+1小的数。其他的牛以此类推。

换句人话 就是直接从后向前跑一下简单的测试用例，就好理解了：

• 第五头牛知道前面有0头牛比自己小，自己当然是1
• 第四头牛知道前面有1头牛比自己小，这还不够，因为还需要知道后面是不是有比自己小的啊！这个好办，因为第五头牛高度是1已经确定，可以不再考虑它，把它从牛群中牵走，它的离开，并不会影响第四头牛的心情，因为第五头本来就是在第四头的后面，它走了，第四头牛的信息"前面有1个比我小" 并没有受到影响，此时，它还是最后一头牛，可以不用考虑后面有比自己小的，直接用前面比我小的信息就够了~！由于第五头把1这个高度拿走了，所以，现在剩下的就是2 3 4 5,前面有1个比自己小,那前面小的肯定是2,自己是3。
• 同理，再把第四头牛牵走，剩下的子问题是一样一样的~
• 用循环啥的一个个牵走吧，问题就解决了

方法① 两重循环枚举

先从后往前枚举每头牛，当枚举到第i头牛时，再从1枚举到n，找到第h[i] + 1个没有使用过(后面已经离开的牛牛)的数，再对该数进行标记(标记此数已被我牛牛占用了)，继续枚举下一头牛，时间复杂度O(n^2)，n<=1e5,超时妥妥的

#include <bits/stdc++.h>
using namespace std;
// 通过了 7/10个数据

const int N = 1e5 + 10;
int h[N];
int st[N];
int ans[N];
int n;

int main() {
    scanf("%d", &n);

    for (int i = 2; i <= n; i++) scanf("%d", &h[i]);
    // 第一个放过，不讨论,输进来也是0，不输也是0

    for (int i = n; i; 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] = 1;         // 标识此位置被某个奶牛占据过了
                ans[i] = j;        // 记录i号奶牛占据的是j号位置
                break;
            }
        }
    }
    for (int i = 1; i <= n; i++) printf("%d\n", ans[i]);
    return 0;
}

方法②、树状数组 + 二分

树状数组的应用:倒序多次查找第k小的数

既然暴力无法过掉所有的用例，就只能考虑优化一下了

假如建立一个全部元素为1的数列，某个位置的数为1代表这个高度还不知道是哪头牛的，那么就 用树状数组维护该数列的前缀和 ，若某个位置的前缀和等于H_{i}+1，此时的下标就是要找的数。选择这个数后，将相应位置的1置0.可以 二分 这个位置。

注：好古怪的思路！为什么st[i]默认初始化=1呢？没被选择过，默认设置为0不是更直观，也不用进行初始化了，岂不更好？ 答：不行！因为st[i]=1后，使用前缀和就可以方便知道这段内有多少个未被占用的数字，为了 照顾前缀和同学，你不能使用st[i]=0,当然，也可以初始化为st[i]=0,找出一个，就设置一个st[i]=1,然后用前缀和算出来已使用个数，再用总数减去已使用个数，反正也挺麻烦~

【单点修改+区间前缀和查询】

在所有满足 sum(x) = k 情况中，通过二分找到最小的 x ，如图所示

时间复杂度 O(nlogn)

CodeI 可选是1，不可选 0

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

const int N = 100010;
int a[N];
int ans[N];
int n;

// 树状数组模板
#define lowbit(x) (x & -x)
typedef long long LL;
int c[N];
void add(int x, int v) {
    while (x < N) c[x] += v, x += lowbit(x);
}
LL sum(int x) {
    LL res = 0;
    while (x) res += c[x], x -= lowbit(x);
    return res;
}

int main() {
    scanf("%d", &n);
    for (int i = 2; i <= n; i++) scanf("%d", &a[i]); // 读入每头奶牛前面有几头奶牛比自己矮
    // 利用树状数组，把1~n之间每个位置设置为1,方便后面用来求前缀和
    for (int i = 1; i <= n; i++) add(i, 1);

    for (int i = n; i; i--) {
        int l = 1, r = n;
        while (l < r) {             // 用二分找出前缀和恰好为a[i] + 1的数
            int mid = (l + r) >> 1; // mid枚举的是下标
            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++) printf("%d\n", ans[i]);
    return 0;
}

CodeII 可选是0，不可选 1

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

const int N = 100010;
int a[N];
int ans[N];
int n;

// 树状数组模板
#define lowbit(x) (x & -x)
typedef long long LL;
int c[N];
void add(int x, int v) {
    while (x < N) c[x] += v, x += lowbit(x);
}
LL sum(int x) {
    LL res = 0;
    while (x) res += c[x], x -= lowbit(x);
    return res;
}
/*
参考答案：
2
4
5
3
1
*/
int main() {
#ifndef ONLINE_JUDGE
    freopen("244.in", "r", stdin);
#endif
    scanf("%d", &n);
    for (int i = 2; i <= n; i++) scanf("%d", &a[i]); // 读入每头奶牛前面有几头奶牛比自己矮

    // 这里是区别！
    // 利用树状数组，把1~n之间每个位置设置为1,方便后面用来求前缀和
    // for (int i = 1; i <= n; i++) add(i, 1);

    for (int i = n; i; i--) {
        int l = 1, r = n;
        while (l < r) { // 用二分找出前缀和恰好为a[i] + 1的数

            // 这里是区别！
            int mid = (l + r) >> 1; // mid枚举的是下标
            if (mid - 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++) printf("%d\n", ans[i]);
    return 0;
}