问题描述

有一个1-n的序列,你只知道在每一位之前有多少个数字比它小,请你求出这个序列。

输入

第一行n,
接下来n-1行,第i行表示在第i个数之前有多少个数比它小。

输出

输出这个序列

思路

不难想到,这个序列我们可以从后往前推。我们设num[i]为第i个数之前有多少个数比它小。

因为最后一个数有num[n]个比它小,那它一定是num[n]+1。然后继续递推倒数第n-1个数,它就是除了num[n]+1中的第num[n-1]+1个数。依次类推,我们这样可以求出整个序列。

这道题有两种实现,一种是树状数组+二分,另一种是权值线段树,详细内容可以看代码。

代码

树状数组+二分

#include <cstdio>
#include <algorithm>
#include <cstring>
#define MAXN 8005
using namespace std;

int n, num[MAXN], t[MAXN], ans[MAXN];

void add(int x, int y) {for(; x<=n; x+=(x&-x)) t[x]+=y;}
int sum(int x) {int y=0; for(; x; x-=(x&-x)) y+=t[x]; return y;} 

int search(int x)
{
    int l=1, r=n, ans;
    while(l<=r)
    {
        int mid=(l+r)/2;
        if(sum(mid)>=x) ans=mid, r=mid-1;
        else l=mid+1;
    }
    return ans;
}

int main()
{
    scanf("%d", &n);
    add(1, 1);
    for(int i=2; i<=n; i++)
    {
        scanf("%d", &num[i]);
        add(i, 1);
    }
    for(int i=n; i>=1; i--)
    {
        ans[i]=search(num[i]+1);
        add(ans[i], -1);
    }
    for(int i=1; i<=n; i++) printf("%d\n", ans[i]);
}

线段树

#include <cstdio>
#include <algorithm>
#include <cstring>
#define MAXN 8005
#define ls (rt<<1)
#define rs (rt<<1|1)
#define mid (l+r>>1)
using namespace std;

int n, num[MAXN], t[MAXN*4], ans[MAXN];

void build(int rt, int l, int r)
{
    t[rt]=r-l+1;
    if(l==r) return;
    build(ls, l, mid);
    build(rs, mid+1, r);
}

int query(int rt, int l, int r, int x)
{
    t[rt]--;
    if(l==r) return l;
    if(x>t[ls]) return query(rs, mid+1, r, x-t[ls]);
    else return query(ls, l, mid, x);
}

int main()
{
    scanf("%d", &n);
    build(1, 1, n);
    for(int i=2; i<=n; i++) scanf("%d", &num[i]);
    for(int i=n; i>=1; i--) ans[i]=query(1, 1, n, num[i]+1);
    for(int i=1; i<=n; i++) printf("%d\n", ans[i]);
}

发表评论

邮箱地址不会被公开。 必填项已用*标注