埃森哲杯第十六届上海大学程序设计联赛春季赛暨上海高校金马五校赛 C序列变换

链接：https://www.nowcoder.com/acm/contest/91/C
来源：牛客网
没有账号的同学这样注册，支持博主

题目描述

给定两个长度为n的序列，a_i, b_i(1<=i<=n), 通过3种魔法使得序列a变换为序列b，也就是a_i=b_i(1<=i<=n).

魔法1：交换a_i和a_j，i!=j

首先通过若干次的魔法1将序列a变换成序列c

魔法2：对1个数乘2或者加1

魔法3：对1个数除以2或者减1，如果是奇数，则不能除以2

若c_i>b_i, 则只能对c_i实施魔法3，若c_i<b_i, 则只能对c_i实施魔法2. 例如c_i=6, b_i=4,

则可以通过对c_i实施2次减1操作(魔法3)将c_i变为b_i, 但不可以对c_i除以2再加1将c_i变为b_i，因为c_i>b_i, 所以不能对c_i实施加1操作(魔法2).

小埃想通过最少的操作次数使得序列a变成序列b，操作次数是指使用的魔法次数。

输入描述:

输入测试组数T，每组数据，第一行输入n，1<=n<=9,紧接着输入两行，每行n个整数，前一行为a₁,a₂,…,a_n,后一行为b₁,b₂,…,b_n.其中1<=a_i,b_i<=10⁸,1<=i<=n.

输出描述:

每组数据输出一个整数，表示最少的操作次数

输入例子:

输出例子:

6

3

-->

示例1

输入

复制

输出

复制

6

3

分析题目，三种操作中，2和3是一样的，1就是交换。
由于N很小很小，可以枚举每种交换的情况。枚举方式：全排列，循环一遍统计生成当前排列所需的交换数。

问题就在于如何求出a[i]通过2或3操作变成b[j]的方案数。
从较大的数向较小的数推，贪心即可求！！！！！具体见代码的calc函数。
这部分需要预处理，如果不预处理的话复杂度加一个log就过不了了。

 /*

 ◇◇◇◇◇◇◇◇◇◇◇◇◇◇◇◇◇◇◇◇◇◇◇◇◇◇◇◇◇◇◇◇◇◇◇◇◇◇◇◇◇◇◇◇◇

 ◇◇◇◇◇◇◆◆◇◇◇◇◇◇◇◇◇◇◇◇◇◇◇◇◇◇◇◇◇◇◇◇◇◇◇◆◇◇◇◇◇◇◇◇◇

 ◇◇◇◇◇◇◆◆◇◇◇◇◇◇◇◇◇◇◇◇◇◇◇◇◇◇◇◇◇◇◇◇◇◇◆◆◇◇◇◇◇◇◇◇◇

 ◇◇◇◇◇◇◇◆◇◇◇◇◇◇◇◇◇◇◇◇◇◇◇◇◇◇◇◇◇◇◇◇◇◇◇◆◇◇◇◇◇◇◇◇◇

 ◇◇◇◇◇◇◇◆◇◇◇◇◇◇◇◇◇◇◇◇◇◇◇◇◇◇◇◇◇◇◇◇◇◇◇◆◇◆◆◆◇◇◇◇◇

 ◇◇◇◇◇◇◇◆◇◇◇◇◇◇◇◇◇◇◇◇◆◆◆◆◆◇◇◇◇◇◇◇◇◇◇◆◆◆◆◆◇◇◇◇◇

 ◇◇◇◇◇◇◇◆◇◇◇◇◇◇◇◇◇◇◇◇◆◆◆◆◆◇◇◇◇◇◇◇◇◇◇◆◆◇◆◆◇◇◇◇◇

 ◇◇◇◇◇◇◇◆◇◇◇◇◇◇◇◇◇◇◇◇◇◇◆◆◇◇◇◇◇◇◇◇◇◇◇◆◇◇◇◆◇◇◇◇◇

 ◇◇◇◇◇◇◇◆◇◇◇◇◇◇◇◇◇◇◇◇◇◆◆◇◇◇◇◇◇◇◇◇◇◇◇◆◇◇◇◆◇◇◇◇◇

 ◇◇◇◇◇◇◇◆◇◇◇◇◇◇◇◇◇◇◇◇◆◆◆◇◆◇◇◇◇◇◇◇◇◇◇◆◇◇◇◆◇◇◇◇◇

 ◇◇◇◇◇◇◆◆◆◆◇◇◇◇◇◇◇◇◇◇◆◆◆◆◆◇◇◇◇◇◇◇◇◇◆◆◆◇◆◆◆◇◇◇◇

 ◇◇◇◇◇◇◇◇◇◇◇◇◇◇◇◇◇◇◇◇◇◇◇◇◇◇◇◇◇◇◇◇◇◇◇◇◇◇◇◇◇◇◇◇◇

 ◇◇◇◇◇◇◇◇◇◇◇◇◇◇◇◇◇◇◇◇◇◇◇◇◇◇◇◇◇◇◇◇◇◇◇◇◇◇◇◇◇◇◇◇◇

 ◇◇◇◇◇◇◇◇◇◇◇◇◇◇◇◇◇◇◇◇◇◇◇◇◇◇◇◇◇◇◇◇◇◇◇◇◇◇◇◇◇◇◇◇◇

 ◇◇◇◇◇◇◇◇◇◇◇◇◇◇◇◇◇◇◇◇◇◇◇◇◇◇◇◇◇◇◇◇◇◇◇◇◇◇◇◇◇◇◇◇◇

 */

 #include<iostream>

 #include<cstdio>

 #include<cstring>

 #include<ctime>

 #include<cstdlib>

 #include<algorithm>

 #include<cmath>

 #include<string>

 using namespace std;

 int read(){

     int xx=,ff=;char ch=getchar();

     while(ch>''||ch<''){if(ch=='-')ff=-;ch=getchar();}

     while(ch>=''&&ch<=''){xx=xx*+ch-'';ch=getchar();}

     return xx*ff;

 }

 int N,a[],b[],c[],t[],lin[],cost[][];

 int calc(int x,int y){

     if(x<y)

         swap(x,y);

     int re=;

     while(x!=y){

         if(x%==){

             if(x/>=y)

                 x/=,re++;

             else

                 re+=x-y,x=y;

         }

         else

             x--,re++;

     }

     return re;

 }

 int main(){

     //freopen("in.txt","r",stdin);

     for(int T=read();T;T--){

         N=read();

         for(int i=;i<=N;i++)

             a[i]=read();

         for(int i=;i<=N;i++)

             b[i]=read();

         for(int i=;i<=N;i++)

             c[i]=i;

         for(int i=;i<=N;i++)

             for(int j=;j<=N;j++)

                 cost[i][j]=calc(a[i],b[j]);

         /*for(int i=1;i<=N;i++){

             for(int j=1;j<=N;j++)

                 printf("%d ",cost[i][j]);

             puts("");

         }*/

         int ans=(1LL<<)-,now;

         do{

             now=;

             for(int i=;i<=N;i++)

                 t[i]=c[i],lin[t[i]]=i;

             for(int i=;i<=N;i++)

                 if(t[i]!=i){

                     int j=lin[i];

                     swap(t[i],t[j]);

                     lin[t[i]]=i;

                     lin[t[j]]=j;

                     now++;

                 }

             for(int i=;i<=N;i++)

                 now+=cost[c[i]][i];

             if(now<ans)

                 ans=now;

         }while(next_permutation(c+,c++N));

         printf("%d\n",ans);

     }

     return ;

 }

秒客网

埃森哲杯第十六届上海大学程序设计联赛春季赛暨上海高校金马五校赛 C序列变换

题目描述

输入描述:

输出描述:

输入例子:

输出例子:

输入

输出

相关文章