P1116 车厢重组

calendar May 6, 2026 · 3 分钟阅读 · 模拟  ·
分享到: linkedin copy

文章目录

题目信息

字段 内容
题号 P1116
难度 橙题（普及-）
知识点 排序、贪心、模拟

题目描述

在一个旧式的火车站旁边有一座桥，其桥面可以绕河中心的桥墩水平旋转。

一个车站职工发现桥的长度最多能容纳两节车厢，如果将桥旋转 180 度，则可以把相邻两节车厢的位置交换，用这种方法可以重新排列车厢的顺序。

于是他就负责用这座桥将进站的车厢按车厢号从小到大的顺序重新排好。

请你帮助他求出交换的最少次数。

输入格式

第一行一个整数 n，表示车厢的总数。

第二行有 n 个整数，分别表示车厢的初始顺序（这些整数均为正整数，且小于等于 100，保证不重复）。

输出格式

一个整数，表示最少交换次数。

解题思路

核心思想

这道题的本质是统计逆序对的数量。

由于每次交换只能交换相邻的两个车厢，而最终要将车厢按从小到大排序，那么：

  • 对于每一对 “前面的数比后面的数大” 的情况（即逆序对），都必须通过至少一次相邻交换来消除
  • 冒泡排序的过程恰好模拟了这个交换过程，每进行一次相邻交换，就消除一个逆序对

因此，最少交换次数 = 逆序对的数量。

算法实现

这是一个选择排序的变体：

  1. 从第 1 个位置开始，依次找出剩余未排序部分中最小的元素
  2. 如果发现更小的元素，就与当前位置交换
  3. 统计交换次数

这种做法虽然不是标准的冒泡排序，但同样能完成排序并正确统计交换次数。

完整代码

C++

#include <iostream>
using namespace std;

int n, a[10001], cnt;

int main() {
    cin >> n;
    for (int i = 1; i <= n; i++) {
        cin >> a[i];
    }
    for (int i = 1; i < n; i++) {
        for (int j = i + 1; j <= n; j++) {
            if (a[j] < a[i]) {
                swap(a[j], a[i]);
                cnt++;
            }
        }
    }
    cout << cnt;
    return 0;
}

关键代码讲解

for (int i = 1; i < n; i++) {
    for (int j = i + 1; j <= n; j++) {
        if (a[j] < a[i]) {
            swap(a[j], a[i]);
            cnt++;
        }
    }
}

这段代码的逻辑是：

  • 外层循环 i 从 1 到 n-1，表示当前位置
  • 内层循环 j 从 i+1 到 n，在后面的元素中寻找比 a[i] 更小的元素
  • 如果找到（说明存在逆序），就进行交换并计数

每执行一次 swap，就消除了一个逆序对，计数器 cnt 记录了总共需要的交换次数。

复杂度分析

方法 时间复杂度 空间复杂度
选择排序变体 O(n^2) O(1)

易错点

  1. 交换的判断条件：必须是 a[j] < a[i]（严格小于），不能写成 <= 或 >
  2. 数组大小：题目保证 n ≤ 100，但代码中使用了 a[10001]，足够容纳所有数据
  3. 计数器的类型：计数器可能达到 n × (n-1) / 2（完全逆序时），最大约 4950，使用 int 类型足够

其他语言解法

Python

import sys

def main():
    data = list(map(int, sys.stdin.read().split()))
    n = data[0]
    a = data[1:1 + n]
    cnt = 0
    
    for i in range(n - 1):
        for j in range(i + 1, n):
            if a[j] < a[i]:
                a[i], a[j] = a[j], a[i]
                cnt += 1
    
    print(cnt)


if __name__ == '__main__':
    main()

Java

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

public class Main {
    public static void main(String[] args) throws IOException {
        // 使用 StreamTokenizer 更高效地解析整数输入
        StreamTokenizer in = new StreamTokenizer(new BufferedReader(new InputStreamReader(System.in)));
        in.nextToken();
        int n = (int) in.nval;
        
        int[] a = new int[n];
        for (int i = 0; i < n; i++) {
            in.nextToken();
            a[i] = (int) in.nval;
        }
        
        int cnt = 0;
        for (int i = 0; i < n - 1; i++) {
            for (int j = i + 1; j < n; j++) {
                if (a[j] < a[i]) {
                    int temp = a[i];
                    a[i] = a[j];
                    a[j] = temp;
                    cnt++;
                }
            }
        }
        
        System.out.println(cnt);
    }
}

Go

package main

import (
    "bufio"
    "fmt"
    "os"
)

func main() {
    in := bufio.NewReader(os.Stdin)
    
    var n int
    fmt.Fscan(in, &n)
    
    a := make([]int, n)
    for i := 0; i < n; i++ {
        fmt.Fscan(in, &a[i])
    }
    
    cnt := 0
    for i := 0; i < n-1; i++ {
        for j := i + 1; j < n; j++ {
            if a[j] < a[i] {
                a[i], a[j] = a[j], a[i]
                cnt++
            }
        }
    }
    
    fmt.Println(cnt)
}

JavaScript

'use strict';

const fs = require('fs');
const input = fs.readFileSync('/dev/stdin', 'utf8').trim().split(/\s+/).map(Number);
const n = input[0];
const a = input.slice(1, n + 1);

let cnt = 0;

for (let i = 0; i < n - 1; i++) {
    for (let j = i + 1; j < n; j++) {
        if (a[j] < a[i]) {
            [a[i], a[j]] = [a[j], a[i]];
            cnt++;
        }
    }
}

console.log(cnt);