本文共 1715 字，大约阅读时间需要 5 分钟。
参考了牛客大佬的代码，真的过了。
贪心策略： a[]数组第i小去匹配b[]数组第i大的数，这样就能使最终得到的sum最小。因此只要找到a[]数组中第i小和b[]数组中第i大的数一起匹配就好了。（一开始搞错了，去让a[]降序，b[]降序，其实不用这样的）
设置a0[]数组，一开始与a[]数组的元素相同，后将a0[]数组进行降序排序，借助a0[]数组给a[]数组每个元素进行编号，同理，b[]数组也按此方法进行编号。然后，遍历a[],b[]数组，如发现a[i]与b[i]编号不同，则固定b[]数组（或a[]数组），找到a[]中编号与b[i]相同的a[k]，a[i]与a[k]进行交换，交换一次，次数cnt++。
然而，最后一步如果按暴力的方式需要两层循环，这样会超时。为了减少一层循环，即减少匹配时间，
我们要另设一个数组pos[]，pos[i]表示：a[]中编号为i的元素在a[]数组中的位置。这样当需要交换时，我们只需直接将a[i]与a[pos[b[i]]]交换就可以了，不过交换后还要对pos[]进行处理，毕竟此时a[]数组已经发生了变化，需将pos[a[i]]与pos[a[pos[b[i]]]]交换。 代码如下：
#include #include #include #include typedef long long ll;using namespace std;ll a0[100005],b0[100005],a[100005],b[100005];ll pos[100005];bool cmp(ll x,ll y){ return x>y;}int find(int x,int y,ll v,int flag){ int m; if(flag==1) { while(x v) y=m; else x=m+1; } } else if(flag==2) { while(x v) x=m+1; else y=m; } } return m;}int main(){ int n,cnt,i,j,temp; scanf("%d",&n); for(i=0;i<=n-1;i++) { scanf("%lld",&a0[i]); a[i]=a0[i]; } for(i=0;i<=n-1;i++) { scanf("%lld",&b0[i]); b[i]=b0[i]; } sort(a0,a0+n); sort(b0,b0+n,cmp); for(i=0;i<=n-1;i++) { temp=find(0,n,a[i],1); a[i]=temp; //a[],b[]里的值没什么用的其实，直接将这两个数组来存储编号就好 temp=find(0,n,b[i],2); b[i]=temp; } for(i=0;i<=n-1;i++) pos[a[i]]=i; cnt=0; for(i=0;i<=n-1;i++) { if(a[i]!=b[i]) { swap(a[i],a[pos[b[i]]]); //先交换a[i],a[pos[b[i]]] swap(pos[a[i]],pos[a[pos[b[i]]]]); //后交换pos[a[i]],pos[a[pos[b[i]]]]，注意，虽然这时a[i],a[pos[b[i]]]的值已经发生变化，但并不影响 cnt++; } } printf("%d\n",cnt); return 0;}/*51 5 4 8 99 6 4 2 3271 9 6 7 3 5 211 42 3 5 9 2 84101 6 7 4 3 2 9 10 5 88 6 10 4 2 7 3 1 5 9721 22 121 22 1*/
此题对本人有较大意义，即在乱序的情况下，通过另外设置一个pos[]数组，记录某一数组编号所在位置，快速的找到编号相同的两个数并交换，需好好掌握。
转载地址：http://mbdci.baihongyu.com/