题面在这里
最终状态一定是一个先增后减的峰形
然后交换次数其实等于 最终状态的\(id\)序列的逆序对数
考虑按高度从小到大加入最终的序列，只能放在两端，分别统计答案，选小的那个
用树状数组维护 未加入的点的\(id\)分布情况
示例程序：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
| #include<cstdio>
#include<algorithm>
using namespace std;
typedef long long ll;
const int maxn=300005;
int n;
struct data{
int x,id;
bool operator<(const data&b)const {return x<b.x;}
}a[maxn];
int b1[maxn],b2[maxn];
#define lowbit(x) ((x)&-(x))
void ist(int x,int w){
for (int i=x;i<=n;i+=lowbit(i)) b1[i]+=w;
for (int i=x;i>=1;i-=lowbit(i)) b2[i]+=w;
}
int qry(int x){
int r1=0,r2=0;
for (int i=x;i>=1;i-=lowbit(i)) r1+=b1[i];
for (int i=x;i<=n;i+=lowbit(i)) r2+=b2[i];
return min(r1,r2);
}
int main(){
scanf("%d",&n);
for (int i=1;i<=n;i++) scanf("%d",&a[i].x),a[i].id=i,ist(i,1);
sort(a+1,a+1+n);
ll ans=0;
for (int i=1,j=1;i<=n;i=j){
for (j=i;j<=n&&a[i].x==a[j].x;j++) ist(a[j].id,-1);
for (j=i;j<=n&&a[i].x==a[j].x;j++) ans+=qry(a[j].id);
}
printf("%lld",ans);
return 0;
}
|
