Description

约翰有n头奶牛，这些奶牛长得很相似，约翰经常分不清谁是谁，于是约翰给他们编号1到n，以此来区分每头奶牛。
今天奶牛们想作弄一下约翰，n头奶牛乱序排成一排。
约翰想要分清每个位置对应奶牛的编号。约翰从左起第2头奶牛开始一直到第n头奶牛，依次问每个奶牛一个问题“你左边有多少个编号比你小的奶牛”，奶牛们都会如实回答约翰的问题。
问，你能否根据奶牛的回答，帮助约翰推出这n头牛对应的编号？

Input Format

第一行，一个整数n
接下来n-1行，每行一个整数，分别表示左起第2到第n头奶牛的回答。

Output Format

n行，每行一个整数，对应从左往右每头奶牛的编号。

Sample Input

5
1
2
1
0

Sample Output

2
4
5
3
1

Hint

1<=N<=50000

首先我们尝试求出每一头奶牛的编号。

显然当前奶牛的编号=左边编号比他小的+右边编号比他小的。

右边编号比它小的有哪些呢？

我们用 $a_i$ 表示第 $i$ 头奶牛左边编号比它小的奶牛的数量。

如果对于奶牛 $i,j,i<j$ 且 $a_i\ge a_j$，那么奶牛 $j$ 的编号一定比奶牛 $i$ 小。

然后我用树状数组写了个程序，30分，WA掉了。

程序如下：

#include <cstdio>
#define lowbit(x) (x & -x)

int c[50005], n, a[50005], ans[50005];

inline int GetSum(int x)
{
    int sum = 0;
    for (int i = x; i > 0; i -= lowbit(i)) sum += c[i];
    return sum; 
}

inline void modify(int x, int d)
{
    for (int i = x; i <= n; i += lowbit(i)) c[i] += d;
}

signed main()
{
    scanf("%d", &n);
    for (int i = 2; i <= n; i ++)
    scanf("%d", a + i);
    for (int i = n; i >= 1; i --)
    {
        ans[i] = a[i] + GetSum(a[i] + 1) + 1;//a[i]不加1的话modify就死了，因为a[i]可能为0
        modify(a[i] + 1, 1);
    }
    for (int i = 1; i <= n; i ++)
    printf("%dn", ans[i]);
}

我自己造的Hack:

Input:

5
0
0
2
1

Output:

5
3
1
4
2

Program Output:

3
2
1
4
2

错误的原因是虽然第五头奶牛比第三头小，但是 $a_5>a_3$，所以没有计入比编号比第三头奶牛小的奶牛中。

同理由于 $a_4>a_1$，虽然第四头奶牛编号比第一头小，但是还是没有计算到。

说明我们的做法有遗漏。

然后我搞了半天也没搞出来正解。。。

回头看一眼数据范围，$n\le 50000$ ？这明显是 $O(nlogn)$ 跑的啊……

其实少爷机跑常数特别低的$O(N^2)$能过50000的……洛谷神机的话开了O2完全没悬念秒过

好像这道题$O(N^2)$暴力常数真就很小？可以去少爷机上试试……

好了，言归正传， $logn$ 肯定是二分分出来的或者说树状数组操作的耗时，也就是说我们还可以浪费一点时间来二分。

二分啥呢？没啥好二分的，干脆直接二分答案吧！

那么如何检查当前考虑的编号是否合法呢？

如果这个这头奶牛右边的编号比他大的加上左边的编号比他大的大于这个编号，那么表示这个编号大了，反之小了。

那么我们就要逆序枚举当前的奶牛，树状数组就要保存遇到过的（在右边的奶牛）的所有编号。

每次在树状数组中就可以查找到这头奶牛右边比这个编号大的奶牛的数量。

不得不说这道题目的解法真的很巧妙啊。

ps:好像复杂度变成了 $O(n(logn{)}^2)$……不过也无伤大雅吧。老爷机也就几十毫秒。

$Code:$

#include <cstdio>
#define lowbit(x) (x & -x)

int c[50005], n, a[50005], ans[50005], L, R, mid;

inline int GetSum(int x)
{
    int sum = 0;
    for (int i = x; i > 0; i -= lowbit(i)) sum += c[i];
    return sum; 
}

inline void modify(int x, int d)
{
    for (int i = x; i <= n; i += lowbit(i)) c[i] += d;
}

int main()
{
    scanf("%d", &n); 
    for (int i = 2; i <= n; i ++)
    scanf("%d", a + i);
    for (int i = n; i >= 1; i --)
    {
        L = 1, R = n;//二分奶牛编号
        while (L <= R)
        {
            mid = L + R >> 1;
            if (GetSum(mid) + a[i] < mid) R = mid - 1;
            else L = mid + 1;
        }
        ans[i] = L;
        modify(L, 1);//每次计算出这头奶牛编号后要将其加到树状数组里面
    }
    for (int i = 1; i <= n; i ++)
    printf("%dn", ans[i]);
    return 0;
}

最后

以上就是神勇黑夜为你收集整理的NKOJ 3709 走丢的奶牛 C o d e : Code: Code:的全部内容，希望文章能够帮你解决NKOJ 3709 走丢的奶牛 C o d e : Code: Code:所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。