/ Vijos / 题库 /

签到题

签到题

背景

PS: Pascal代码

procedure bubble_sort(n:longint);
var
i,j,x:longint;
begin
for i:=0 to n-1 do
for j:=0 to n-1 do
if a[j]>a[j+1] then
begin
x:=a[j];
a[j]:=a[j+1];
a[j+1]:=x;
end;
end;

描述

这是一道良心的签到题。
冒泡排序大家都会。
对于一个有 N 个元素的排列 A ,你需要选择任意两个元素交换一次且仅一次,得到新序列 A' ,使 A‘ 用以下冒泡排序排序时的交换次数最小,输出答案。

void bubble_sort(int a, int n)
{
int i, j;
for (i = 0; i < n - 1; i ++)
{
for (j = 0; j < n - 1; j ++)
{
if (a[j] > a[j + 1])
{
/
你懂得…………*/
int x = a[j];
a[j] = a[j + 1];
a[j + 1] = x;
}
}
}
}

格式

输入格式

第一行一个整数 N 。
第二行 N 个整数 Ai 。

输出格式

输出一个数表示答案。

样例1

样例输入1

5
10
3
6
8
1

样例输出1

0

样例2

样例输入2

5
3
1
7
9
5

样例输出2

2

样例3

样例输入3

3
1
2
3

样例输出3

1

限制

对于 10% 的数据:
1 ≤ N ≤ 1 000

对于 100% 的数据:
1 ≤ N ≤ 100 000
1 ≤ Ai ≤ 1 000 000 000

提示

样例解释1:
A'={1, 3, 6, 8, 10} 已经有序,冒泡排序时不需交换
2:
A'={1, 3, 2} (注意必须数列A必须进行一次交换得到A')冒泡排序交换了一次

来源

布吉岛。

信息

ID
1893
难度
9
分类
(无)
标签
(无)
递交数
432
已通过
23
通过率
5%
上传者

相关

在下列训练计划中:

RP++分类题库

在下列比赛中:

Deplore NOIP模拟赛