2 条题解
-
0
#include<bits/stdc++.h> using namespace std; const int N=1e5+10; int n,a[N],h[N],c[N]; void add(int x,int k){for(;x<=n;x+=x&-x)c[x]+=k;} int sum(int x){int s=0;for(;x;x-=x&-x)s+=c[x];return s;} int main() { scanf("%d",&n); for(int i=2;i<=n;i++)scanf("%d",&a[i]); memset(c,0,sizeof(c)); for(int i=1;i<=n;i++)add(i,1); for(int i=n;i>=1;i--) { int l=1,r=n,t=0;//t=0以防找不到mid while(l<=r) { int mid=(l+r)>>1; if(sum(mid)<a[i]+1)l=mid+1,t=mid; else r=mid-1; } add(h[i]=t+1,-1); } for(int i=1;i<=n;i++)printf("%d\n",h[i]); return 0; } -
0
#include<bits/stdc++.h> using namespace std; const int N=1e5+10; int n,a[N],h[N],c[N]; void add(int x,int k){for(;x<=n;x+=x&-x)c[x]+=k;} int sum(int x){int s=0;for(;x;x-=x&-x)s+=c[x];return s;} int main() { scanf("%d",&n); for(int i=2;i<=n;i++)scanf("%d",&a[i]); memset(c,0,sizeof(c)); for(int i=1;i<=n;i++)add(i,1); for(int i=n;i>=1;i--) { int l=1,r=n,t=0;//t=0以防找不到mid while(l<=r) { int mid=(l+r)>>1; if(sum(mid)<a[i]+1)l=mid+1,t=mid; else r=mid-1; } add(h[i]=t+1,-1); } for(int i=1;i<=n;i++)printf("%d\n",h[i]); return 0; }
- 1
信息
- ID
- 1326
- 时间
- 1000ms
- 内存
- 64MiB
- 难度
- 5
- 标签
- 递交数
- 80
- 已通过
- 33
- 上传者