题目大意

给出一个大小为n的数组，求稳定排序后第a大与第b大的原始下标之差。

思路

定义一个结构体，一个值记录值，一个记录原始坐标，写一个结构体自定义排序，排序之后，输出第a个和第b个结构体的原始坐标之差即可

代码如下

cpp

#include <bits/stdc++.h>
using namespace std;
#define N 100005

int n, a, b; // 数组长度n，排名a和b
struct node { 
    int w, id; // w表示元素的值, id表示元素的原始下标
} num[N];

// 比较函数，用于从大到小排序，同时保持稳定性
int cmp(node a, node b) {
    if (a.w == b.w) return a.id < b.id; // 值相同则按原始下标排序
    return a.w > b.w; // 值不同则按值从大到小排序
}

int main() {
    // 输入数组长度n，排名a和b
    cin >> n >> a >> b;
    
    // 读取数组中的每个元素
    for (int i = 1; i <= n; i++) {
        cin >> num[i].w; // 读取元素值
        num[i].id = i;   // 记录元素的原始下标
    }
    
    // 稳定排序，按照值从大到小排序
    sort(num + 1, num + n + 1, cmp);
    
    // 输出排名a和排名b的元素在原数组中的下标差的绝对值
    cout << abs(num[a].id - num[b].id) << '\n';
    
    return 0;
}

python

# 定义结构体 node，存储元素值和原始下标
class node:
    def __init__(self, w, id):
        self.w = w  # 元素值
        self.id = id  # 元素的原始下标

# 自定义比较函数，用于从大到小排序，同时保持稳定性
def compare(e):
    return (-e.w, e.id)

# 读取输入
n, a, b = map(int, input().split())  # 输入n, a, b
num = [None]  # 索引从1开始，所以num[0]占位
nums = list(map(int, input().split()))  # 读取数组中的所有元素

# 将每个元素和原始下标存入num数组
for i in range(1, n + 1):
    num.append(node(nums[i - 1], i))

# 稳定排序，按照值从大到小排序
num[1:] = sorted(num[1:], key=compare)  # 从1开始排序

# 输出排名a和排名b的元素在原数组中的下标差的绝对值
distance = abs(num[a].id - num[b].id)
print(distance)

java

import java.util.Arrays;
import java.util.Scanner;

public class Main {

    // 定义结构体 node，存储元素值和原始下标
    static class node implements Comparable<node> {
        int w; // 元素值
        int id; // 元素的原始下标

        public node(int w, int id) {
            this.w = w;
            this.id = id;
        }

        // 比较函数，用于从大到小排序，同时保持稳定性
        @Override
        public int compareTo(node other) {
            if (this.w == other.w) {
                return this.id - other.id; // 值相同则按原始下标排序
            }
            return other.w - this.w; // 值不同则按值从大到小排序
        }
    }

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);

        // 输入数组长度n，排名a和b
        int n = scanner.nextInt();
        int a = scanner.nextInt();
        int b = scanner.nextInt();

        // 读取数组中的每个元素
        node[] num = new node[n + 1]; // +1 因为从1开始
        for (int i = 1; i <= n; i++) {
            int w = scanner.nextInt();
            num[i] = new node(w, i); // 保存元素值和原始下标
        }

        // 稳定排序，按照值从大到小排序
        Arrays.sort(num, 1, n + 1);

        // 输出排名a和排名b的元素在原数组中的下标差的绝对值
        System.out.println(Math.abs(num[a].id - num[b].id));

        scanner.close();
    }
}

题目内容

给定一个长度为$n$的数组，你需要对这个数组进行稳定地排序(从大到小排序)。稳定的排序指的是对于相同元素而言，排序前位置在前面的元素在排序后的位置仍然在前面。

排序之后每一个元素有一个确定的排名，现在要求你输出排名为$a$ 的元素和排名为$b$的元素在排序之前的距离是多少。

输入描述

第一行包含三个正整数 $n, a, b$，分别表示数组的长度$n$和两个需要计算距离的元素排名$a$和$b$($1 ≤ a, b ≤ n ≤ 10^5$)。

第二行包含$n$个正整数$num_i$，表示数组中的每一个数字($1 ≤ num_i ≤ 10^5$)

输出描述

输出一行整数表示答案。

样例1

输入

5 3 5
4 2 3 1 5

输出

2

说明

在排序后，排名为$3$和$5$的元素在原数组中的位置分别为$3$和$5$，距离为 $|3 - 5| = 2$。