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;
}
全部评论

相关推荐

2 收藏 评论
分享
牛客网
牛客企业服务