门户网站建设模板下载,多店铺商城系统开源,网站制作案例效果,淄博网站建设专家链接#xff1a;https://www.nowcoder.com/acm/contest/91/C来源#xff1a;牛客网没有账号的同学这样注册#xff0c;支持博主 题目描述 给定两个长度为n的序列#xff0c;ai, bi(1in), 通过3种魔法使得序列a变换为序列b#xff0c;也就是aibi(1in). 魔…链接https://www.nowcoder.com/acm/contest/91/C来源牛客网没有账号的同学这样注册支持博主 题目描述 给定两个长度为n的序列ai, bi(1in), 通过3种魔法使得序列a变换为序列b也就是aibi(1in). 魔法1 交换ai和aji!j 首先通过若干次的魔法1将序列a变换成序列c 魔法2 对1个数乘2或者加1 魔法3 对1个数除以2或者减1如果是奇数则不能除以2 若cibi, 则只能对ci实施魔法3若cibi, 则只能对ci实施魔法2. 例如ci6, bi4, 则可以通过对ci实施2次减1操作(魔法3)将ci变为bi, 但不可以对ci除以2再加1将ci变为bi因为cibi, 所以不能对ci实施加1操作(魔法2). 小埃想通过最少的操作次数使得序列a变成序列b 操作次数是指使用的魔法次数。 输入描述: 输入测试组数T每组数据第一行输入n1n9,紧接着输入两行每行n个整数前一行为a1,a2,…,an,后一行为b1,b2,…,bn.其中1ai,bi108,1in. 输出描述: 每组数据输出一个整数表示最少的操作次数 示例1 输入 复制 2
2
8 7
5 1
4
4 3 1 3
1 1 4 3 输出 复制 6
3分析题目三种操作中2和3是一样的1就是交换。由于N很小很小可以枚举每种交换的情况。枚举方式全排列循环一遍统计生成当前排列所需的交换数。问题就在于如何求出a[i]通过2或3操作变成b[j]的方案数。从较大的数向较小的数推贪心即可求具体见代码的calc函数。这部分需要预处理如果不预处理的话复杂度加一个log就过不了了。 1 /*2 ◇◇◇◇◇◇◇◇◇◇◇◇◇◇◇◇◇◇◇◇◇◇◇◇◇◇◇◇◇◇◇◇◇◇◇◇◇◇◇◇◇◇◇◇◇3 ◇◇◇◇◇◇◆◆◇◇◇◇◇◇◇◇◇◇◇◇◇◇◇◇◇◇◇◇◇◇◇◇◇◇◇◆◇◇◇◇◇◇◇◇◇4 ◇◇◇◇◇◇◆◆◇◇◇◇◇◇◇◇◇◇◇◇◇◇◇◇◇◇◇◇◇◇◇◇◇◇◆◆◇◇◇◇◇◇◇◇◇5 ◇◇◇◇◇◇◇◆◇◇◇◇◇◇◇◇◇◇◇◇◇◇◇◇◇◇◇◇◇◇◇◇◇◇◇◆◇◇◇◇◇◇◇◇◇6 ◇◇◇◇◇◇◇◆◇◇◇◇◇◇◇◇◇◇◇◇◇◇◇◇◇◇◇◇◇◇◇◇◇◇◇◆◇◆◆◆◇◇◇◇◇7 ◇◇◇◇◇◇◇◆◇◇◇◇◇◇◇◇◇◇◇◇◆◆◆◆◆◇◇◇◇◇◇◇◇◇◇◆◆◆◆◆◇◇◇◇◇8 ◇◇◇◇◇◇◇◆◇◇◇◇◇◇◇◇◇◇◇◇◆◆◆◆◆◇◇◇◇◇◇◇◇◇◇◆◆◇◆◆◇◇◇◇◇9 ◇◇◇◇◇◇◇◆◇◇◇◇◇◇◇◇◇◇◇◇◇◇◆◆◇◇◇◇◇◇◇◇◇◇◇◆◇◇◇◆◇◇◇◇◇
10 ◇◇◇◇◇◇◇◆◇◇◇◇◇◇◇◇◇◇◇◇◇◆◆◇◇◇◇◇◇◇◇◇◇◇◇◆◇◇◇◆◇◇◇◇◇
11 ◇◇◇◇◇◇◇◆◇◇◇◇◇◇◇◇◇◇◇◇◆◆◆◇◆◇◇◇◇◇◇◇◇◇◇◆◇◇◇◆◇◇◇◇◇
12 ◇◇◇◇◇◇◆◆◆◆◇◇◇◇◇◇◇◇◇◇◆◆◆◆◆◇◇◇◇◇◇◇◇◇◆◆◆◇◆◆◆◇◇◇◇
13 ◇◇◇◇◇◇◇◇◇◇◇◇◇◇◇◇◇◇◇◇◇◇◇◇◇◇◇◇◇◇◇◇◇◇◇◇◇◇◇◇◇◇◇◇◇
14 ◇◇◇◇◇◇◇◇◇◇◇◇◇◇◇◇◇◇◇◇◇◇◇◇◇◇◇◇◇◇◇◇◇◇◇◇◇◇◇◇◇◇◇◇◇
15 ◇◇◇◇◇◇◇◇◇◇◇◇◇◇◇◇◇◇◇◇◇◇◇◇◇◇◇◇◇◇◇◇◇◇◇◇◇◇◇◇◇◇◇◇◇
16 ◇◇◇◇◇◇◇◇◇◇◇◇◇◇◇◇◇◇◇◇◇◇◇◇◇◇◇◇◇◇◇◇◇◇◇◇◇◇◇◇◇◇◇◇◇
17 */
18 #includeiostream
19 #includecstdio
20 #includecstring
21 #includectime
22 #includecstdlib
23 #includealgorithm
24 #includecmath
25 #includestring
26 using namespace std;
27 int read(){
28 int xx0,ff1;char chgetchar();
29 while(ch9||ch0){if(ch-)ff-1;chgetchar();}
30 while(ch0ch9){xxxx*10ch-0;chgetchar();}
31 return xx*ff;
32 }
33 int N,a[10],b[10],c[10],t[10],lin[10],cost[10][10];
34 int calc(int x,int y){
35 if(xy)
36 swap(x,y);
37 int re0;
38 while(x!y){
39 if(x%20){
40 if(x/2y)
41 x/2,re;
42 else
43 rex-y,xy;
44 }
45 else
46 x--,re;
47 }
48 return re;
49 }
50 int main(){
51 //freopen(in.txt,r,stdin);
52 for(int Tread();T;T--){
53 Nread();
54 for(int i1;iN;i)
55 a[i]read();
56 for(int i1;iN;i)
57 b[i]read();
58 for(int i1;iN;i)
59 c[i]i;
60 for(int i1;iN;i)
61 for(int j1;jN;j)
62 cost[i][j]calc(a[i],b[j]);
63 /*for(int i1;iN;i){
64 for(int j1;jN;j)
65 printf(%d ,cost[i][j]);
66 puts();
67 }*/
68 int ans(1LL31)-1,now;
69 do{
70 now0;
71 for(int i1;iN;i)
72 t[i]c[i],lin[t[i]]i;
73 for(int i1;iN;i)
74 if(t[i]!i){
75 int jlin[i];
76 swap(t[i],t[j]);
77 lin[t[i]]i;
78 lin[t[j]]j;
79 now;
80 }
81 for(int i1;iN;i)
82 nowcost[c[i]][i];
83 if(nowans)
84 ansnow;
85 }while(next_permutation(c1,c1N));
86 printf(%d\n,ans);
87 }
88 return 0;
89 } View Code 转载于:https://www.cnblogs.com/lzhAFO/p/9119575.html
