序列变换(暴力+贪心)

描述

传送门:埃森哲杯第十六届上海大学程序设计联赛春季赛暨上海高校金马五校赛 - Problem E

给定两个长度为$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_1,a_2,…,a_n$,后一行为$b_1,b_2,…,b_n$。其中$1≤ai,bi≤10^8$,$1≤i≤n$。

输出

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

样例输入

1
2
3
4
5
6
7
2
2
8 7
5 1
4
4 3 1 3
1 1 4 3

样例输出

1
2
6
3

思路

  • 看到数据范围,那么想到$n \le 9$只要next_permutation枚举全排列。魔法1的使用次数就得到了。
  • 注意到魔法2和魔法3的操作是对称的,于是可以对大的数贪心:能除以$2$就除以$2$,否则减$1$。
  • 可以$O(n^2)$预处理两两使用魔法2或者魔法3的次数。
  • 细节比较多,不过写起来还是比较简单的。但是现场赛过的人不多。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
#include <bits/stdc++.h>
using namespace std;
#define clr(a, x) memset(a, x, sizeof(a))
#define mp(x, y) make_pair(x, y)
#define pb(x) push_back(x)
#define X first
#define Y second
#define fastin \
ios_base::sync_with_stdio(0); \
cin.tie(0);
typedef long long ll;
typedef long double ld;
typedef pair<int, int> PII;
typedef vector<int> VI;
const int INF = 0x3f3f3f3f;
const int mod = 1e9 + 7;
const double eps = 1e-6;

const int N = 10;
int a[N], b[N], id[N];
bool vis[N];
int ch[N][N];

void dfs(int x, int& cnt)
{
if (vis[x]) return;
vis[x] = 1, cnt++;
dfs(id[x], cnt);
}

int magic1(int n)
{
int ret = 0;
clr(vis, 0);
for (int i = 0; i < n; i++)
{
if (vis[i]) continue;
int cnt = 0;
dfs(i, cnt);
ret += cnt - 1;
}
return ret;
}

int magic2(int x, int y)
{
int ret = 0;
if (x < y) swap(x, y);
while (x / 2 >= y)
{
ret += (x & 1) + 1;
x >>= 1;
}
ret += x - y;
return ret;
}

int gao(int n)
{
int ret = magic1(n);
for (int i = 0; i < n; i++) ret += ch[id[i]][i];
return ret;
}

int main()
{
#ifndef ONLINE_JUDGE
freopen("1.in", "r", stdin);
freopen("1.out", "w", stdout);
#endif
int T;
scanf("%d", &T);
while (T--)
{
int n;
scanf("%d", &n);
iota(id, id + n, 0);
for (int i = 0; i < n; i++) scanf("%d", a + i);
for (int i = 0; i < n; i++) scanf("%d", b + i);
for (int i = 0; i < n; i++)
for (int j = 0; j < n; j++) ch[i][j] = magic2(a[i], b[j]);
int ans = INF;
do
ans = min(ans, gao(n));
while (next_permutation(id, id + n));
printf("%d\n", ans);
}
return 0;
}
捐助作者
0%