文章目录
一.题目二.Solution三.CodeThanks!
一.题目
传送门
二.Solution
这道题目主要是理解题目，题目中冒泡排序到底是怎么排的？其实就是从第一个数开始将其交换到最后一个比它小的数的位置，将这期间的长度累加就是答案了。 考虑什么时候排序完成，就是每个数之间都有一个分隔点出现的时候就排序完成了。我们将
i
i
i与
i
+
1
i+1
i+1之间的分隔点保存在
i
i
i点上，用
t
[
i
]
t[i]
t[i]数组表示分隔点
i
i
i出现的时间，当且仅当一个点两边都出现了分隔点时排序结束，所以每个点的答案就是
m
a
x
(
t
[
i
]
,
t
[
i
+
1
]
)
max(t[i], t[i+1])
max(t[i],t[i+1])。 考虑怎么求？ 先离散化数组，处理每个数最远的比他小的数和他的距离，这个可以用单调队列等，但我没用，直接用一个变量存比当前数小的最远位置，直接减当前数的位置就行了。
三.Code
#include <cstdio>
#include <cstring>
#include <iostream>
#include <map>
#include <algorithm>
using namespace std
;
#define M 100005
#define LL long long
struct node
{
int v
, id
;
}a
[M
];
int n
;
LL ans
, t
[M
];
bool cmp
(node a
, node b
){
if (a
.v
== b
.v
)
return a
.id
< b
.id
;
return a
.v
< b
.v
;
}
int main
(){
scanf
("%d", &n
);
for (int i
= 1; i
<= n
; i
++){
scanf
("%d", &a
[i
].v
);
a
[i
].id
= i
;
}
sort
(a
+ 1, a
+ 1 + n
, cmp
);
int maxn
= 0;
for (int i
= 1; i
<= n
; i
++){
maxn
= max
(maxn
, a
[i
].id
);
t
[i
] = max
(1, maxn
- i
);
}
for (int i
= 1; i
<= n
; i
++)
ans
+= max
(t
[i
], t
[i
- 1]);
printf
("%lld\n", ans
);
return 0;
}
Thanks!
