刷题记录:牛客NC51101Lost Cows

传送门:牛客

题目描述:

(2≤N≤8,000) cows have unique brands in the range 1..N. In a spectacular display of poor judgment, 
they visited the neighborhood 'watering hole' and drank a few too many beers before dinner. When it 
was time to line up for their evening meal, they did not line up in the required ascending numerical 
order of their brands.
Regrettably, FJ does not have a way to sort them. Furthermore, he's not very good at observing 
problems. Instead of writing down each cow's brand, he determined a rather silly statistic: For each 
cow in line, he knows the number of cows that precede that cow in line that do, in fact, have smaller 
brands than that cow.
Given this data, tell FJ the exact ordering of the cows.
输入
5
1
2
1
0
输出:
2
4
5
3
1

方法一

首先本题有一个比较显然的解决方法,我们可以从最后一个人开始为他定编号,因为对于最后一个人来说,如果他选了$a$编号,那么对于它的前面的人来说,此时除了$a$,所有剩下的编号肯定都是有的,那么就说明我们现在的$a$编号在我们剩下的所有的编号的位置(从小到大)就是当前这个人前面比他小的个数+1.

那么此时我们的问题就变成了如何找出一段序列中排名为$k$的数字,并且支持单点删除操作.对于这个问题,我在这道题中有详细的解释,所以此处就不在赘述了.具体可参考代码

下面是具体的代码部分:

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define root 1,n,1
#define ls rt<<1
#define rs rt<<1|1
#define lson l,mid,rt<<1
#define rson mid+1,r,rt<<1|1
inline ll read() {ll x=0,w=1;char ch=getchar();for(;ch>'9'||ch<'0';ch=getchar()) if(ch=='-') w=-1;for(;ch>='0'&&ch<='9';ch=getchar()) x=x*10+ch-'0';return x*w;
}
#define maxn 1000000
const double eps=1e-8;
#define	int_INF 0x3f3f3f3f
#define ll_INF 0x3f3f3f3f3f3f3f3fc
struct Segment_tree{int l,r,sum;
}tree[maxn];
int n;
void pushup(int rt) {tree[rt].sum=tree[ls].sum+tree[rs].sum;
}
void build(int l,int r,int rt) {tree[rt].l=l;tree[rt].r=r;if(l==r) {tree[rt].sum=1;return ;}int mid=(tree[rt].l+tree[rt].r)>>1;build(lson);build(rson);pushup(rt);
}
void update(int pos,int rt) {if(tree[rt].l==pos&&tree[rt].r==pos) {tree[rt].sum=0;return ;}int mid=(tree[rt].l+tree[rt].r)>>1;if(pos<=mid) update(pos,ls);else update(pos,rs);pushup(rt);
}
int query(int l,int r,int rt,int k) {if(tree[rt].l==tree[rt].r) return tree[rt].l;int mid=(tree[rt].l+tree[rt].r)>>1;if(tree[ls].sum>=k) return query(l,mid,ls,k);else return query(mid+1,r,rs,k-tree[ls].sum);
}
int ans[maxn];int a[maxn];
int main() {n=read();build(root);for(int i=2;i<=n;i++) a[i]=read();for(int i=n;i>=2;i--) {ans[i]=query(1,n,1,a[i]+1);update(ans[i],1);}ans[1]=query(1,n,1,1);for(int i=1;i<=n;i++) {printf("%d\n",ans[i]);}return 0;
}

方法二

我们可以反向的去思考这道题.我们此时考虑对排在前$i$位的人分配我们的相对编号大小.那么对于第$i$个人来说,我们之前的所有$i-1$位人显然都是排在这个人前面的,所以我们要将第$i$个人插在$i-1$排好的编号之中,并且满足当前的需求即可.因为对于插入操作来说,我们并不影响之前的$i-1$的相对编号大小.

以样例为例(下标为编号):
对于第一只奶牛，在它之前没有奶牛，所以编号为1：1
对于第二只奶牛，在它之前有1只奶牛编号比它小，所以编号为2：1 2
对于第三只奶牛，在它之前有2只奶牛编号比它小，在它之前实际也只有两只奶牛，所以编号为3：1 2 3
对于第四只奶牛，由样例，在它之前有1只奶牛编号比它小，而在他前面有三个奶牛,所以此时它的编号应该大于三个奶牛中的两个,所以此时将他的编号赋为4,其他奶牛编号顺延：1 4 2 3
对于第五只奶牛,解决方法同第四只,编号赋值为1：5 1 4 2 3

对于插入操作,最优的写法显然是链表,但是由于此题的数据不多,才$8000$,所以此时我们直接使用$vector$来进行维护依旧是可以接受的,复杂度为$n\ast (n+1)/2$,差不多为$3e7$左右

下面是具体的代码部分:

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define root 1,n,1
#define ls rt<<1
#define rs rt<<1|1
#define lson l,mid,rt<<1
#define rson mid+1,r,rt<<1|1
inline ll read() {ll x=0,w=1;char ch=getchar();for(;ch>'9'||ch<'0';ch=getchar()) if(ch=='-') w=-1;for(;ch>='0'&&ch<='9';ch=getchar()) x=x*10+ch-'0';return x*w;
}
#define maxn 1000000
const double eps=1e-8;
#define	int_INF 0x3f3f3f3f
#define ll_INF 0x3f3f3f3f3f3f3f3f
vector<int>v;
int a;int ans[maxn];
int main() {int n=read();v.insert(v.begin(),1);for(int i=2;i<=n;i++) {a=read();v.insert(v.begin()+a,i);}for(int i=0;i<v.size();i++) {ans[v[i]]=i+1;}for(int i=1;i<=n;i++) {cout<<ans[i]<<endl;}return 0;
}