NC15570. 序列变换
描述
给定两个长度为n的序列，ai, bi(1<=i<=n), 通过3种魔法使得序列a变换为序列b，也就是ai=bi(1<=i<=n).
魔法1： 交换ai和aj，i!=j
首先通过若干次的魔法1将序列a变换成序列c
魔法2： 对1个数乘2或者加1
魔法3： 对1个数除以2或者减1，如果是奇数，则不能除以2
若ci>bi, 则只能对ci实施魔法3，若ci<bi, 则只能对ci实施魔法2. 例如ci=6, bi=4,
则可以通过对ci实施2次减1操作(魔法3)将ci变为bi, 但不可以对ci除以2再加1将ci变为bi，因为ci>bi, 所以不能对ci实施加1操作(魔法2).
小埃想通过最少的操作次数使得序列a变成序列b， 操作次数是指使用的魔法次数。
输入描述
输入测试组数T，每组数据，第一行输入n，1<=n<=9,紧接着输入两行，每行n个整数，前一行为a1,a2,…,an,后一行为b1,b2,…,bn.其中1<=ai,bi<=108,1<=i<=n.
输出描述
每组数据输出一个整数，表示最少的操作次数
示例1
输入:
2 2 8 7 5 1 4 4 3 1 3 1 1 4 3
输出:
6 3
C++11(clang++ 3.9) 解法, 执行用时: 1011ms, 内存消耗: 616K, 提交时间: 2018-04-15 15:42:53
#include<bits/stdc++.h>
using namespace std;
int t,n,x,i,a[10],b[10],p[10],q[10],r[10],o[65536],ans;
int ask(int x)
{
if(x<65536)return o[x];
return o[x>>16]+o[x&65535];
}
int ask(int a,int b)
{
if(a>b)swap(a,b);
int i=0,j=1<<30;
for(;i<30;i++)if(b>>i>=a)j=min(j,ask(b&((1<<i)-1))+i+(b>>i)-a);
else break;
return j;
}
int main()
{
scanf("%d",&t);
for(i=1;i<65536;i++)o[i]=o[i>>1]+(i&1);
while(t--)
{
scanf("%d",&n);
for(i=1;i<=n;i++)scanf("%d",a+i);
for(i=1;i<=n;i++)scanf("%d",b+i);
for(i=1;i<=n;i++)p[i]=i;
ans=1<<30;
do
{
for(i=1;i<=n;i++)q[i]=p[i];
for(i=1;i<=n;i++)r[q[i]]=i;
x=0;
for(i=1;i<=n;i++)if(q[i]!=i)
{
x++;
r[q[i]]=r[i];
swap(q[r[i]],q[i]);
r[i]=i;
}
for(i=1;i<=n;i++)x+=ask(a[p[i]],b[i]);
ans=min(ans,x);
}while(next_permutation(p+1,p+n+1));
cout<<ans<<endl;
}
return 0;
}