小米oj 帮小学生排队（排序+插入）

帮小学生排队

序号：#18难度：有挑战时间限制：1000ms内存限制：10M

描述

用一个数组表示一群正在排队的小学生，每个小学生用一对整数 H, K 来表示：H 表示这个小学生的身高，K 表示这个小学生前面应该有 K 个人的身高 >= 他。

写一个算法，对给出的一组小学生计算出符合描述的正确排序。

输入

输入为一组整数，以空格分隔：

第 1 个数字表示小学生的数量 n；从第 2 个数字起，后续的数字两两一组，分别代表每个小学生的 H 和 K 的值：H_1\text{ }K_1\text{ }H_2\text{ }K_2 \cdots H_n\text{ }K_nH1​K1​H2​K2​⋯Hn​Kn​.

输出

根据输入，按照题目要求对小学生进行排序，每个小学生对应的 H 和 K 值为一组，按组输出，数字间使用空格分隔。比如H_1'\text{ }K_1'\text{ }H_2'\text{ }K_2' \cdots H_n' \text{ }K_n'H1′​K1′​H2′​K2′​⋯Hn′​Kn′​

输入样例

6 7 0 4 4 7 1 5 0 6 1 5 2

复制样例

输出样例

5 0 7 0 5 2 6 1 4 4 7 1

#include<bits/stdc++.h>#include<stdio.h>#include<iostream>#include<cmath>#include<math.h>#include<queue>#include<set>#include<map>#include<iomanip>#include<algorithm>#include<stack>using namespace std;#define inf 0x3f3f3f3ftypedef long long ll;int n;int id[1000];int h[1000];int k[1000];bool cmp(int i,int j){if(h[i]!=h[j])return h[i]>h[j];else return k[i]<k[j];}int ans[1000];void ins(int i,int len){int pos=k[i];for(int j=len;j>pos;j--)ans[j]=ans[j-1];ans[pos]=i;}int main(){#ifndef ONLINE_JUDGEfreopen("in.txt","r",stdin);#endif // ONLINE_JUDGEwhile(cin>>n){for(int i=0;i<n;i++)cin>>h[i]>>k[i];for(int i=0;i<n;i++)id[i]=i;sort(id,id+n,cmp);memset(ans,-1,sizeof(ans));for(int i=0;i<n;i++){ins(id[i],i);}for(int i=0;i<n;i++)cout<<h[ans[i]]<<" "<<k[ans[i]]<<" ";cout<<endl;}return 0;}