題干：

鏈接：https://ac.nowcoder.com/acm/contest/551/E
來源：牛客網

有兩個長度為 n 的序列，a0,a1,…,an?1a0,a1,…,an?1和 b0,b1,…,bn?1b0,b1,…,bn?1。CSL 有一種魔法，每執行一次魔法，可以任意挑選一個序列并任意交換序列中兩個元素的位置。CSL 使用若干次魔法，得到最終的序列 a 和 b，并且想要讓 a0b0+a1b1+…+an?1bn?1a0b0+a1b1+…+an?1bn?1的值最小化。求解 CSL 至少使用多少次魔法，能夠達到最小化的目標。

輸入描述:

第一行有一個整數 n，表示序列的長度。接下來兩行，每行有 n 個整數，分別表示初始序列 a 和 b。

輸入數據保證每個序列里的數兩兩不同。

?

2≤n≤1052≤n≤105
1≤ai,bi≤1091≤ai,bi≤109

輸出描述:

在一行輸出一個整數，表示最少使用的魔法次數。

示例1

輸入

復制

2 1 2 1 2

輸出

復制

1

示例2

輸入

復制

2 1 2 2 1

輸出

復制

0

解題報告：

? 首先通過貪心不難證明，當兩個數組分別是最大值和最小值匹配的時候，這樣剛好達到最小值。所以就是怎么通過最小步數讓a數組可以從大到小排列就可以了。

? 那么后面這一步的實現方法就很多了。該AC代碼只是提供了一種方式。還可以用離散數學中置換群的概念來理解（如果沒記錯應該是叫這個），大概一堆概念什么對換變換置換一類操作，，具體忘記了，總之就是可以得出一堆環來，每個環之間的數一次替換就可以排列好，也就是分成若干個塊，塊間不影響。。（因為你換一次操作至少能對齊一個吧，就是你換走的這個。當然如果巧合，換過來的這個剛好就是你需要的，那就完美了，對于這個塊的操作就結束了）。對于上述步驟，可以利用該思想暴力，也可以直接算出這個塊中有多少數字，假設涉及x個數字，然后直接(x-1)就是答案。。又因為總塊數是n，那么換句話說，只需要數出有多少個塊cnt，然后n-cnt就是答案。

AC代碼：

#include<cstdio> #include<iostream> #include<algorithm> #include<queue> #include<map> #include<vector> #include<set> #include<string> #include<cmath> #include<cstring> #define ll long long #define pb push_back #define pm make_pair using namespace std; const int MAX = 2e5 + 5; int a[MAX],b[MAX],aa[MAX],bb[MAX]; map<int,int> mp,mb;//mb存b數組每個數字的位置。 mp存本應該在的位置 int main() {int n;cin>>n;for(int i = 1; i<=n; i++) cin>>a[i],aa[i] = a[i];for(int i = 1; i<=n; i++) cin>>b[i],mb[b[i]] = i;sort(aa+1,aa+n+1);sort(b+1,b+n+1,greater<int>());for(int i = 1; i<=n; i++) mp[aa[i]] = mb[b[i]];int ans = 0;for(int i = 1; i<=n; i++) {while(mp[a[i]]!=i) swap(a[i],a[mp[a[i]]]),ans++;}printf("%d\n",ans);return 0 ; }

AC代碼2：（分塊的方法，省掉了map，跑的飛快）?

#include <bits/stdc++.h> using namespace std;typedef pair<int, int> pii; #define ff first #define ss second #define mp make_pairint main() {ios::sync_with_stdio(false);cin.tie(nullptr);int n;cin >> n;vector<pii> ab(n);vector<int> next(n);vector<bool> vis(n, false);for (int i = 0; i != n; ++i) cin >> ab[i].ff;for (int i = 0; i != n; ++i) cin >> ab[i].ss;sort(ab.begin(), ab.end());for (int i = 0; i != n; ++i) ab[i].ff = i;//映射到新值1~n內sort(ab.begin(), ab.end(), [] (const pii& x, const pii& y) { return x.ss > y.ss; });for (int i = 0; i != n; ++i) next[i] = ab[i].ff;int res = 0;for (int i = 0; i != n; ++i) if (!vis[i]) {++res;while (!vis[i]) {vis[i] = true;i = next[i];}}cout << n - res << endl; }

?

總結

以上是生活随笔為你收集整理的【牛客 - 551E】CSL 的魔法（贪心，思维，STLmap，分块）的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。