Codeforces Round #101 (Div. 2)C. Queue

题目链接

题意：给定n个人以及每个人前面比他高的人数a[i]。让你还原这个队列及每个人的高度。

题解：

按照a排序，然后给这n个人分配身高，显然a大的人的身高尽可能低，所以身高高度从n到1进行分配。

然后让每个人进行入队，对于第i个人，考虑其入队情况。根据身高分配规则可知，队列中的每个人都比其要高。然后将i插入到a[i]的位置即可，此时满足i前面比i高的人个数为a[i]，并且i入队不改变队列中的原本的a。

#include<bits/stdc++.h>
#define LL long long
#define pii pair<int,int>
#define psi pair<string,int>
using namespace std;
const int N = ;
struct node{
    string name;
    int a;
    bool operator <(node b)const{
        return a<b.a;
    }
}p[N];
int s[N];
void out(int x){
    cout<<x;
    exit();
}
int main()
{
    freopen("a.txt","r",stdin);
    ios::sync_with_stdio();
    int n,i,j;
    cin>>n;
    for(i = ;i <= n;i ++) s[i] = i;
    for(i = ;i <= n;i ++)
        cin>>p[i].name>>p[i].a;
    sort(p+,p+n+);
    vector<psi>ans;
    for(i = ;i <= n;i ++){
       if(p[i].a>=i)out(-);
       ans.insert(ans.begin()+p[i].a,make_pair(p[i].name,n-i+));
    }
    for(auto v:ans)
        cout<<v.first<<' '<<v.second<<endl;
    return ;
}