MIOJ #18 帮小学生排队

描述

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

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

输入

输入为一组整数,以空格分隔:

  • 第 1 个数字表示小学生的数量 n;
  • 从第 2 个数字起,后续的数字两两一组,分别代表每个小学生的 H 和 K 的值

输出

根据输入,按照题目要求对小学生进行排序,每个小学生对应的 H 和 K 值为一组,按组输出,数字间使用空格分隔。

输入样例

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

AC代码:

#include <bits/stdc++.h>
#include<vector>
#include<stack>
#include<sstream>
using namespace std;

typedef struct student{
     int h;
     int k;
};

int comp(const student &a,const student &b){
    if(a.h == b.h){
        return a.k < b.k;
    }
    return a.h>b.h;
}

int main(){
   int n;
   while(cin>>n){
    student stu[n+1];
    for(int i = 0; i<n ;i++){
        cin>>stu[i].h>>stu[i].k;
    }
      sort(stu,stu+n,comp);
     vector<student>a;
     for(int i = 0;i<n;i++){
        a.insert(a.begin()+stu[i].k,stu[i]);
     }
     cout<<a[0].h<<" "<<a[0].k;
     for(int i = 1;i<n;i++){
        cout<<" "<<a[i].h<<" "<<a[i].k;
     }
      cout<<endl;
   }
}

 

发表评论

您的电子邮箱地址不会被公开。 必填项已用*标注