CoolCool的序列

链接
来源：牛客网

题目描述

Cg特别喜欢翻转序列！

跨年夜也要继续翻转！

现在有一个长度为n的序列s，Cg将其翻转之后变成了t。

路过的oxy发现了这个t序列，但是oxy不可以直接将序列翻转，她只可以执行一种操作：

选择任意的两个数a_i和a_j(j>i)，花费j−i将两数位置交换

问oxy最少花费多少对Cg的 s 进行操作 可以得到Cg的 t 呢？

输入描述:

一个整数N,代表序列的长度，（1<=N<=100000）
接下来N个整数代表序列s，1<=a_i <= N

输出描述:

oxy的最小花费~

输入

4
1 2 3 4

输出

4

翻转之后t = {4,3,2,1}，只需要交换1 4 与 2 3 便可得到 4 3 2 1，花费为4

示例2

输入

5
1 1 2 3 1

输出

2

说明

翻转之后t = {1,3,2,1,1}
s = {1,1,2,3,1}，交换2 4之后 s = {1,3,2,1,1}
所以花费为2

想到某一个操作是否会对其他操作有贡献上去了, 一直不对, 还是太菜了

题解:
对于每种数字, 建立一个桶, 存放位置的值, 再建立另一个桶, 存放反转后位置的值, 求得就是第二个桶里的数字的排列, 使得两个桶对应位置的值的差的绝对值最小, 显然就是让两个桶从小到大排列, 这样就最小了.

int n,a[MAXN],b[MAXN];
ll ans;
queue<int>p[MAXN];
int main(){
    read(n);
    for(int i=1;i<=n;++i)read(a[i]);
    for(int i=n;i>=1;--i)p[a[i]].push(n-i+1);
    for(int i=1;i<=n;++i){
        ans+=abs(i-p[a[i]].front());
        p[a[i]].pop();
    }
    printf("%lld",ans>>1);
    return 0;
}