🍭 大家好这里是清隆学长 ，一枚热爱算法的程序员

✨ 本系列打算持续跟新华为OD-C/D卷的三语言AC题解

💻 ACM银牌🥈| 多次AK大厂笔试 ｜ 编程一对一辅导

👏 感谢大家的订阅➕ 和 喜欢💗

📎在线评测链接

https://app5938.acapp.acwing.com.cn/contest/2/problem/OD1058

🌍 评测功能需要 ⇒ 订阅专栏 ⇐ 后私信联系清隆解锁～

🍓OJ题目截图

🪐 身高差值排序

问题描述

K小姐和她的同学们身高都不太一样。她想按照每个同学与自己的身高差值的绝对值进行从小到大排序。如果两个同学与 K小姐身高差值的绝对值相等,那么身高较矮的同学排在前面。现在请你帮助 K小姐实现这个身高差值排序。

输入格式

第一行包含两个正整数 $H$ 和 $N$,其中 $0<H<200$ 表示 K小姐的身高,$0<N<50$ 表示其他同学的人数。

第二行包含 $N$ 个正整数 $H_1$ ~ $H_N$,表示其他每个同学的身高,满足 $0<H_i<200$ ($1\le i\le N$),且所有的 $H_i$ 互不相同。

输出格式

输出身高差值排序后的结果,每个数之间用一个空格隔开。

样例输入

100 10
95 96 97 98 99 101 102 103 104 105

样例输出

99 101 98 102 97 103 96 104 95 105

数据范围

• $0<H<200$
• $0<N<50$
• $0<H_i<200$ ($1\le i\le N$)

题解

本题主要考察了对结构体的使用以及自定义排序规则。我们可以将每个同学的身高 $H_i$ 与 K小姐的身高差值的绝对值 $|H-H_i|$ 作为第一关键字,身高 $H_i$ 作为第二关键字,构建结构体并自定义排序规则,然后将所有同学按照这个规则进行排序即可。

对于 C++ 语言,我们可以使用 pair<int,int> 来存储 $(|H-H_i|,H_i)$,然后对 pair 进行排序;
对于 Java 语言,我们可以自定义一个类 Student,然后实现 Comparable 接口,重写 compareTo 方法来定义排序规则;
对于 Python 语言,我们可以使用 (|H-H_i|,H_i) 作为元组直接进行排序。

最后将排序后的结果依次输出即可。

参考代码

• Python

h, n = map(int, input().split())
heights = list(map(int, input().split()))
diffs = [(abs(h - x), x) for x in heights]
diffs.sort()
print(' '.join(map(str, [x[1] for x in diffs])))

• Java

import java.io.*;
import java.util.*;

class Student implements Comparable<Student> {
    int diff;
    int height;
    
    public Student(int diff, int height) {
        this.diff = diff;
        this.height = height;
    }
    
    @Override
    public int compareTo(Student other) {
        if (this.diff != other.diff) {
            return Integer.compare(this.diff, other.diff);
        } else {
            return Integer.compare(this.height, other.height);
        }
    }
}

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int H = sc.nextInt();
        int N = sc.nextInt();
        Student[] students = new Student[N];
        for (int i = 0; i < N; i++) {
            int height = sc.nextInt();
            students[i] = new Student(Math.abs(H - height), height);
        }
        Arrays.sort(students);
        for (Student student : students) {
            System.out.print(student.height + " ");
        }
    }
}

• Cpp

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

int main() {
    int h, n;
    cin >> h >> n;
    vector<pair<int, int>> students;
    for (int i = 0; i < n; i++) {
        int height;
        cin >> height;
        students.emplace_back(abs(h - height), height);
    }
    sort(students.begin(), students.end());
    for (auto student : students) {
        cout << student.second << " ";
    }
    return 0;
}