Lost Cows(模拟)
Lost Cows
https://ac.nowcoder.com/acm/problem/51101
题意
有n(2<=n<=8000)只奶牛,每只奶牛都有一个1到n的编号;站成一排,对于第i只奶牛,给出在它之前且编号小于它的奶牛的数量,求这一排每只奶牛的编号。(由于第一只奶牛前面一定没有奶牛,故输入仅给出n-1个数)
解题思路
看到dalao们在用主席树,二分+树状数组,我只能说,我不会啊啊啊!!〒▽〒
但是,不要停下来啊
我们来模拟一下样例,一共有5只奶牛,我们记录一下放入的是第几只奶牛
对于第一只奶牛,在它之前没有奶牛,便直接放入:1
对于第二只奶牛,由样例,在它之前有1只奶牛编号比它小,在它之前实际也只有一只奶牛,便排到末尾:1 2
对于第三只奶牛,由样例,在它之前有2只奶牛编号比它小,在它之前实际也只有两只奶牛,便排到末尾:1 2 3
对于第四只奶牛,由样例,在它之前有1只奶牛编号比它小,但它之前实际有三只奶牛,且这三只奶牛的编号也是从小到大排列的,那它是不是按照编号从小到大,它应该排到这个队列的第二个位置去:1 4 2 3
对于第五只奶牛,由样例,在它之前没有只奶牛编号比它小,但它之前实际有四只奶牛,则它应该排到队首:5 1 4 2 3
接下来我们发现,上面我们将样例按编号从小到大排了一遍,那是不是这个序列的下标就是这只奶牛的编号,而元素的值是这只奶牛在样例序列中的位置啊(~ ̄▽ ̄)~
思维就这么多,剩下的就是敲代码了
AC代码
#include <bits/stdc++.h> using namespace std; vector<int> vec; int ans[10010]; int main() { ios::sync_with_stdio(false); cin.tie(0); cout.tie(0); int n,x; cin>>n; vec.push_back(1); for(int i=2;i<=n;i++){ cin>>x; int tmp=i-x-1; //cout<<tmp<<endl; //cout<<i<<endl; vec.insert(vec.end()-tmp,i); } for(int i=0;i<vec.size();i++) ans[vec[i]]=i+1; for(int i=1;i<=n;i++) cout<<ans[i]<<'\n'; return 0; }