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

#X261108F. 相邻换位

相邻换位

题目描述

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

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

输入格式

首先输入一个整数 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 次。

相关

在下列比赛中:

全栈考核