题解

题目描述

小美有一个长度为 $n$ 的数组 $a$，数组中所有元素的值不相同，且数组的下标从 $1$ 开始。

她计划对这个数组中的每个元素进行“数数”，首先会从数组中数值最小的元素的索引开始，每次数数时，她会选择下一个值刚好大于当前元素值的位置，直到所有元素都被数过为止。

例如，假设数组 $a = [1,3,5]$，小美一开始选择的是索引 $i=1$ （此时 $a_1=1$），她会接着找到第一个比 $1$ 大的元素 $3$（索引 $i=2$），然后再找到第一个比 $3$ 大的元素 $5$（索引 $i=3$）。整个数数过程为：$a_1 \to a_2 \to a_3$。

在这一过程中，如果小美的操作是从较小索引移动到较大索引（即 $j > i$），我们称之为正向传送；如果是从较大索引移动到较小索引（即 $j < i$），则称之为逆向传送。

你的任务是帮助小美计算她在整个数数过程中需要进行多少次正向传送和多少次逆向传送。

思路

1. 理解过程

   • 因为数组中所有元素互不相同，所以可以对值进行从小到大的排序。
   • 小美每次“数数”都是从当前元素值，跳到下一个更大的元素值，直到遍历到最大值为止。
   • 换句话说，整个过程就是沿着“值的升序”在数组中“扫描”一次，但实际上「移动」的顺序是：先定位最小值所在的下标，然后依次按照数值从小到大的顺序，依次跳转到下一个值所在的下标。

2. 计算正向 / 逆向传送

   • 先把数组元素与它们的下标做成 $(a_i,\, i)$ 这样的一对，然后按照 $a_i$ 进行升序排序。
   • 排序后得到一个序列：
     $(v_1,\, p_1),\,(v_2,\, p_2),\,\dots,\,(v_n,\, p_n)$ 其中 $v_1 < v_2 < \dots < v_n$，对应的 $p_k$ 就是值 $v_k$ 在原数组中的下标。
   • 初始从 $p_1$ （最小值）开始，然后按顺序从 $p_1 \to p_2 \to p_3 \to \dots \to p_n$。
   • 对于每一对相邻的 $(v_{k},p_{k})$ 和 $(v_{k+1},p_{k+1})$，比较 $p_{k}$ 与 $p_{k+1}$ ：
     • 如果 $p_{k+1} > p_{k}$，则是一次正向传送。
     • 如果 $p_{k+1} < p_{k}$，则是一次逆向传送。
   • 最终统计所有 $k=1,2,\dots,n-1$ 时的正向和逆向次数即可。

3. 复杂度分析

   • 每组数据需要把 $n$ 个元素连同下标一起打包并排序，时间复杂度为 $O(n\log n)$。
   • 然后线性扫描一遍，计数 正向/逆向 $O(n)$。
   • 由于 $\sum n \le 2\times10^5$，因此所有测试总体复杂度为 $O\bigl((\sum n)\log(\sum n)\bigr)$，是可以接受的。

C++

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

int main() {
    ios::sync_with_stdio(false); // 关闭与 C 标准库同步，加快 I/O
    cin.tie(nullptr);            // 解除 cin 与 cout 的绑定，提升 I/O 性能

    int T;
    if (!(cin >> T)) return 0;   // 读取测试组数，如果读取失败则退出

    while (T--) {
        int n;
        cin >> n;                // 读取当前测试用例中的数组长度 n

        vector<pair<int,int>> vec;
        vec.reserve(n);
        for (int i = 0; i < n; ++i) {
            int x;
            cin >> x;            // 读取第 i 个元素的值
            // 保存 (value, 原始下标)，下标从 1 开始
            vec.emplace_back(x, i + 1);
        }

        // 使用稳定排序，按照 value 升序排列
        stable_sort(vec.begin(), vec.end(),
                    [](const pair<int,int>& a, const pair<int,int>& b) {
                        return a.first < b.first;
                    });

        long long forward = 0;   // 正向传送计数
        long long backward = 0;  // 逆向传送计数

        // 遍历排序后相邻的元素，比较原始下标
        for (int i = 1; i < n; ++i) {
            if (vec[i].second > vec[i - 1].second) {
                // 如果当前元素的原始下标 > 前一个元素的原始下标，则视为正向传送
                ++forward;
            } else {
                // 否则视为逆向传送
                ++backward;
            }
        }

        // 输出结果：正向传送次数 和 逆向传送次数
        cout << forward << " " << backward << "\n";
    }

    return 0;
}

Python

import sys
import threading

def main():
    data = sys.stdin.read().strip().split()
    T = int(data[0])
    idx = 1

    for _ in range(T):
        n = int(data[idx])
        idx += 1

        # 读取 n 个整数
        arr = list(map(int, data[idx:idx + n]))
        idx += n

        # 构造 (value, original_index) 对
        vec = []
        for i, v in enumerate(arr, start=1):
            vec.append((v, i))

        # 按照 value 升序排序
        vec.sort(key=lambda x: x[0])

        forward = 0
        backward = 0

        # 扫描相邻对，比较原下标
        for k in range(1, n):
            if vec[k][1] > vec[k - 1][1]:
                # 当前位置下标大于前一个，正向传送
                forward += 1
            else:
                # 否则逆向传送
                backward += 1

        # 输出结果
        print(forward, backward)

if __name__ == "__main__":
    # 为了加速，大输入时用 threading 避免 RecursionError
    threading.Thread(target=main).start()

Java

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.io.IOException;
import java.util.StringTokenizer;
import java.util.Arrays;

public class Main {
    // 定义一个简单的 Pair 类来保存 (value, index)
    static class Pair implements Comparable<Pair> {
        int value;
        int index;
        Pair(int v, int i) {
            value = v;
            index = i;
        }
        // 按 value 升序排序
        @Override
        public int compareTo(Pair other) {
            return Integer.compare(this.value, other.value);
        }
    }

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        int T = Integer.parseInt(st.nextToken());  // 读取测试组数

        while (T-- > 0) {
            st = new StringTokenizer(br.readLine());
            int n = Integer.parseInt(st.nextToken());  // 读取 n

            st = new StringTokenizer(br.readLine());
            Pair[] vec = new Pair[n];
            for (int i = 0; i < n; i++) {
                int x = Integer.parseInt(st.nextToken());
                // 记录数值以及原始下标 (下标从 1 开始)
                vec[i] = new Pair(x, i + 1);
            }

            // 按 value 升序排序
            Arrays.sort(vec);

            long forward = 0;   // 正向传送次数
            long backward = 0;  // 逆向传送次数

            // 遍历相邻对，比较下标大小
            for (int i = 1; i < n; i++) {
                if (vec[i].index > vec[i - 1].index) {
                    // 下标增加 => 正向传送
                    forward++;
                } else {
                    // 下标减少 => 逆向传送
                    backward++;
                }
            }

            // 输出本组结果
            System.out.println(forward + " " + backward);
        }
    }
}

题目内容

小美有一个长度为 $n$ 的数组 $a$ ，数组中所有元素的值不相同，且数组的下标从 $1$ 开始。

她计划对这个数组中的每个元素进行“数数”，始会从数组中数值最小的元素的素引开始，每次数数时，她会选将第一个值大于当前位置元素值的元素，直到所有元素都被数过为止。

例如，假设数组 $a=[1,3,5]$ ，小美一开始选择的是索引 $i=2$ (此时 $a_2=1$ )，她会接着找到第一个比 $1$ 大的元素 $3$ (索引 $i=1$ )，然后再找到第一个比 $3$ 大的元素 $5$ (索引 $i=3$ )。整个数数过程为： $a_2→a_1→a_3$。

在这一过程中，如果小美的操作是从较小索引移动到较大索引(即 $j>i$ )，我们称之为正向传送；如果是从较大索引移动到较小索引(即 $j＜i$ )，则称之为逆向传送。

你的任务是帮助小美计算她在整个数数过程中需要进行多少次正向传送和多少次逆向传送。

输入描述

每个测试文件均包含多组测试数。第一行输入一个整数 $T(1≤T≤1000)$ 代表数据组数，每组测试数据描述如下：

第一行一个整数 $n(1≤n≤2×10^5)$ ，表示数组长度。

第二行 $n$ 个整数，第 $i$ 个数为 $a_i(1≤a_i≤10^5)$ ，表示数组元素。

单个测试文件 $∑ n≤2×10^5$

输出描述

共 $T$ 行，每行两个整数，分别表示正向传送和逆向传送的次数，以空格隔开。

样例1

输入

2
3
1 2 3
3
3 2 1

输出

2 0
0 2