CoolCool的序列

連結：https://ac.nowcoder.com/acm/contest/9854/G

來源：牛客網

Cg特别喜歡翻轉序列！

跨年夜也要繼續翻轉！

現在有一個長度為n的序列s，Cg将其翻轉之後變成了t。

路過的oxy發現了這個t序列，但是oxy不可以直接将序列翻轉，她隻可以執行一種操作：

選擇任意的兩個數a_i和a_j(j>i)，花費j-i将兩數位置交換選擇任意的兩個數a

i

​

和a

j

​

(j>i)，花費j−i将兩數位置交換

詢問oxy最少花費多少對Cg的 s 進行操作 可以得到Cg的 t 呢？

輸入描述:

一個整數N,代表序列的長度，（1<=N<=100000）

接下來N個整數代表序列s，1<=a_i <= N

輸出描述:

oxy的最小花費~

示例1

輸入

複制

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

#include <iostream>
#include <algorithm>
#include <cstring>
#include <string>
#include <queue>
#include <map>
#include <stack>
#include <cmath>
using namespace std;
#define max(a, b) ((a) > (b) ? (a) : (b))
#define min(a, b) ((a) < (b) ? (a) : (b))
#define x first
#define y second
typedef __int128 INT;
typedef long long LL;
typedef unsigned long long ULL;
typedef pair<int, int> PII;
typedef pair<LL, LL> PLL;
const int N = 1e1 + 10;
const int Mod = 1e9 + 7;
const int inf = 0x3f3f3f3f;
const LL INF = 0x3f3f3f3f3f3f3f3f;
const int P = 13331;
int a[N], b[N];
queue<int> ver[N];
int main(){
		int n;
		scanf("%d", &n);
				for (int i = 1; i <= n; i ++)       scanf("%d", &a[i]);
				for (int i = 1; i <= n; i ++){
			b[i] = a[n - i + 1];
			ver[b[i]].push(i);
		}
				int ans = 0;
				for (int i = 1; i <= n; i ++){
			int x = ver[a[i]].front();
			ver[a[i]].pop();
						//cout << x - i << "--------" << endl;
			ans += abs(x - i);
		}
				ans /= 2;
				cout << ans << endl;
		return 0;
}