跳到主要内容
图灵 OJTURING / ONLINE JUDGE

F. 相邻换位

  • 传统题
  • 2000ms
  • 256MiB

相邻换位

该比赛已结束,您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

题目描述

一列货运车厢需要按编号从小到大排列。操作设备每次只能选取 相邻的两节车厢,交换它们的位置,这算一次操作。

给定初始编号顺序,求排好整列车厢所需的最少操作次数。所有编号互不相同;编号的具体大小不影响排列要求。

输入格式

首先输入一个整数 NN,表示车厢数。随后输入 NN 个互不相同的整数,表示从前到后的编号顺序。编号可能分布在多行中,用空白字符分隔。

输出格式

输出一个整数,表示最少操作次数。

数据范围与计分

1≤N≤10001\le N\le1000,每个编号在 11 至 10910^9 之间,且互不相同。

本题满分 100 分,各测试点独立、等额计分。

样例 1

3
3 1 2
2

样例说明

先交换前两节,得到 1、3、2;再交换后两节,得到 1、2、3,共 2 次。

全栈考核

未参加
状态
已结束
规则
IOI
题目
7
开始于
2026-11-8 19:00
结束于
2026-11-8 21:30
持续时间
2.5 小时
主持人
参赛人数
6