AcWing 3425：小白鼠排队 ← 北京大学考研机试题

本文主要是介绍AcWing 3425：小白鼠排队 ← 北京大学考研机试题，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

【题目来源】
https://www.acwing.com/problem/content/3428/

【题目描述】
N 只小白鼠，每只鼠头上戴着一顶有颜色的帽子。
现在称出每只白鼠的重量，要求按照白鼠重量从大到小的顺序输出它们头上帽子的颜色。
帽子的颜色用 red，blue 等字符串来表示。
不同的小白鼠可以戴相同颜色的帽子。
白鼠的重量用整数表示。

【输入格式】
第一行为一个整数 N，表示小白鼠的数目。
下面有 N 行，每行是一只白鼠的信息。第一个为不大于 100 的正整数，表示白鼠的重量；第二个为字符串，表示白鼠的帽子颜色，字符串长度不超过 10 个字符。
注意：白鼠的重量各不相同。

【输出格式】
按照白鼠的重量从大到小的顺序输出白鼠的帽子颜色。

【数据范围】
1≤N≤100

【输入样例】
3
30 red
50 blue
40 green

【输出样例】
blue
green
red

【算法分析】
一、本题的一种实现方法需要按结构体某一字段对结构体数组进行排序，详见：
https://blog.csdn.net/hnjzsyjyj/article/details/120184972
例如，若自定义的结构体 Person 的内容如下：

struct Person {string name;int age;float height;
};

则可自定义的递增函数 up()、递减函数 down() 的内容如下：

int up(Person u,Person v) { //ascending by heightif(u.height==v.height) return u.name<v.name; //If equal,ascending by namereturn u.height<v.height;
}int down(Person u,Person v) { //descending by heightif(u.height==v.height) return u.name>v.name; //If equal,descending by namereturn u.height>v.height;
}

若 p 为结构体数组，则在主函数中调用递增函数 up()、递减函数 down() 的代码如下：

sort(p,p+n,up); //Sort the structured array p by ascending field heightsort(p,p+n,down); //Sort the structured array p by descending field height

二、本题的另一种实现方法是利用STL pair，然后调用 sort() 函数对 STL pair 进行排序。需要注意的是，sort() 函数默认是按照 pair 的 first 域进行升序排序。如果 first 域相同，则按照 second 域进行升序排序。
若 p 为 pair 数组，则对其 first 域默认进行升序排序的代码如下：

sort(p,p+n); //By default, ascending by the first field of array p

【算法代码一：结构体排序】

#include <bits/stdc++.h>
using namespace std;
const int maxn=105;struct node {int w;string color;
} a[maxn];bool down(node a,node b){return a.w>b.w; //descending by weight
}int main(){int n;cin>>n;for(int i=1;i<=n;i++){cin>>a[i].w>>a[i].color;}sort(a+1,a+1+n,down);for(int i=1;i<=n;i++){cout<<a[i].color<<endl;}
}/*
in:
3
30 red
50 blue
40 greenout:
blue
green
red
*/

【算法代码二：STL pair】

#include <bits/stdc++.h>
using namespace std;const int maxn=105;
pair<int,string> q[maxn];int main() {int n;cin>>n;for(int i=0; i<n; i++) {cin>>q[i].first>>q[i].second;}sort(q,q+n); //By default, ascending by the first fieldfor(int i=n-1; i>=0; i--) {cout<<q[i].second<<endl;}return 0;
}/*
in:
3
30 red
50 blue
40 greenout:
blue
green
red
*/

【参考文献】
https://blog.csdn.net/hnjzsyjyj/article/details/120184972
https://blog.csdn.net/qq_27538633/article/details/126441458





 

这篇关于AcWing 3425：小白鼠排队 ← 北京大学考研机试题的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---