傳送門 题意：给你2*n个数，其中每一个数都有一个和他相等的数，共有n个不同的数。现在让你将每个相等的数排在一起，每次只能交换相邻的数，问最少需要交换几次。 思路：先想什么是优解，必然是先将每一个坐标为1,3,5位置上的数固定（这些都是不需要动的，以它们为参照），这必然是最优坐标，剩下的就是去寻找后面的和该位置上相等的数。先找到相等的数所对应的坐标，然后从后向前不断与前方的数交换位置即可。
/** * From: * Qingdao Agricultural University * Created by XiangwangAcmer * Date : 2019-10-31-10.12.37 * Talk is cheap.Show me your code. */ #include<iostream> #include<cstring> #include<algorithm> #include<cstdio> #include<cstdlib> #include<queue> #include<cmath> #include<cctype> #include<stack> #include<map> #include<string> #include<cstdlib> #define ll long long using namespace std; const ll maxn = 1e6 + 5; const ll minn = 1e9 + 5; const ll mod = 1000000007; const int INF = 0x3f3f3f3f; const long long LIMIT = 4294967295LL; vector<int>v[maxn]; int dp[maxn]; vector<int>G[maxn]; bool row[maxn], col[maxn]; bool flag = 0; queue<int>q; int a[maxn]; int main() { ios::sync_with_stdio(false); int n; cin >> n; for(int i = 1; i <= 2 * n; i++) { cin >> a[i]; } int cnt = 0; for(int i = 1; i <= 2*n; i+=2) ///先找出第一个所在的位置的元素是什么，再从后面找和他相同的元素的坐标，然后那个坐标从后往前遍历。 { int flag = a[i]; for(int j = i + 1; j <= 2*n; j++) { if(a[j] == flag) { for(int k = j; k >= i + 2 ; k--) { swap(a[k],a[k-1]); cnt++; } } } } cout << cnt << endl; return 0; }