#Pbit18. 2.交换序列

    ID: 187 传统题 1000ms 256MiB 尝试: 0 已通过: 0 难度: 普及+/提高- 上传者: 标签>树状数组赛制:OI来源:wyfoj http://127.0.0.1

2.交换序列

2.交换序列

题目描述

有一个有n个数的序列,每次操作可以交换序列中相邻的两个元素。

求使序列变为最长不下降之序列的最小操作数。

输入格式

第一行为一个整数n,表示序列长度

第二行为n个整数,表示序列中每个元素。

输出格式

一个整数ans,即最少操作次数。

数据范围

(原站未提供,导入后需人工补齐)

样例

4
2 8 0 3
3

提示

开始序列为2 8 0 3,目标序列为0 2 3 8,可进行三次操作的目标序列:

交换第2个数和第3个数 :2 0 8 3

交换第1个数和第2个数:0 2 8 3

交换第3个数和第4个数:0 2 3 8

对于30对于30%的数据1<=n<=10^4。

对于100对于100%的数据1<=n<=5*10^5。