[题解]牛的编号(POJ2182)
USSENTERPRISE
·
·
个人记录
1. 题目大意
# 暴力解法
建立一个链表，每次根据大小关系从链表头部遍历插入
代码如下
```cpp
//AC 1144K 532ms
#include<bits/stdc++.h>
using namespace std;
#define rg register
#define ll long long
#define ull unsigned long long
namespace Enterprise{
inline int read(){
rg int s=0,f=0;
rg char ch=getchar();
while(not isdigit(ch)) f|=(ch=='-'),ch=getchar();
while(isdigit(ch)) s=(s<<1)+(s<<3)+(ch^48),ch=getchar();
return f?-s:s;
}
struct Node{
Node* nxt;
int val,id;
Node(){ nxt=NULL; val=0; }
};
Node* head=new Node;
int n;
const int N=8015;
int ans[N];
inline void main(){
n=read();
Node* first=new Node;
first->id=1;
head->nxt=first;
for(rg int i=1;i<n;i++){
Node* now=new Node;
rg int x=read();
now->id=i+1;
Node* vis=new Node;
vis=head;
for(rg int i=1;i<=x;i++,vis=vis->nxt);
now->nxt=vis->nxt;
vis->nxt=now;
}
rg int i=1;
for(Node *now=head->nxt;now;now=now->nxt,i++){
ans[now->id]=i;
}
for(rg int i=1;i<=n;i++){
printf("%d ",ans[i]);
}
}
}
signed main(){
Enterprise::main();
return 0;
}
```
~~OI生涯中第一次写对指针不RE，好开森~~
~~略显笨拙~~
# 正解
权值线段树
本题说人话就是给出一个整数$n$，给出一个数列$\{a_n\}$，$a_i$代表除已选出数外区间$[1,n]$第$a_i$大。
所以我们就可以使用权值线段树较快解决此问题。
思路：每点代表一个区间，存放的数据为当前此区间内可供选择的数的数量。每次进行二分查找就可以得到答案
注意：由题意可得，前面的数有可能会影响后面的数，所以在选数顺序上，应注意采用倒序遍历，使其不会受到已选出的书的影响。
```cpp
//作者在考试的时候傻了，打的大暴力
//(尽管作者当时已经学习了主席树的思想
//AC 732K 110ms
#include<bits/stdc++.h>
using namespace std;
#define rg register
#define ll long long
#define ull unsigned long long
namespace Enterprise{
inline int read(){
rg int s=0,f=0;
rg char ch=getchar();
while(not isdigit(ch)) f|=(ch=='-'),ch=getchar();
while(isdigit(ch)) s=(s<<1)+(s<<3)+(ch^48),ch=getchar();
return f?-s:s;
}
const int N=8015;
int tree[N<<2],n,a[N],ans[N];
#define ls (now<<1)
#define rs (now<<1|1)
#define mid ((l+r)>>1)
inline void pushup(int now){ tree[now]=tree[ls]+tree[rs]; }
inline void build(int now,int l,int r){
if(l==r){ tree[now]=1; return;}
build(ls,l,mid);
build(rs,mid+1,r);
pushup(now);
}
inline int query(int now,int l,int r,int x){
if(l==r){ tree[now]--; return l; }
rg int ans;
if(x<=tree[ls]) ans=query(ls,l,mid,x);
else ans=query(rs,mid+1,r,x-tree[ls]);
pushup(now);
return ans;
}
inline void main(){
n=read();
build(1,1,n);
a[1]=1;
for(rg int i=2;i<=n;i++) a[i]=read()+1;
for(rg int i=n;i>=1;i--)
ans[i]=query(1,1,n,a[i]);
for(rg int i=1;i<=n;i++)
printf("%d\n",ans[i]);
}
}
signed main(){
Enterprise::main();
return 0;
}
```