| 题目名称 | 2163. [UVA 11163]豹王 |
|---|---|
| 输入输出 | uva11163.in/out |
| 难度等级 | ★★☆ |
| 时间限制 | 3000 ms (3 s) |
| 内存限制 | 128 MiB |
| 测试数据 | 10 |
| 题目来源 |
 mikumikumi
于2016-03-01加入 |
| 开放分组 | 全部用户 |
| 提交状态 | |
| 分类标签 | |
| 分享题解 |
| 通过：2， 提交：4， 通过率：50% | ||||
 rewine |
100 | 1.797 s | 0.32 MiB | C++ |
 mikumikumi |
100 | 4.386 s | 0.26 MiB | C++ |
|
rewine |
10 | 2.311 s | 0.31 MiB | C++ |
|
rewine |
10 | 27.001 s | 0.70 MiB | C++ |
| 关于 豹王 的近10条评论(全部评论) | ||||
|---|---|---|---|---|
|
h=Σg[i,a[i]](g[i,j]代表从第i个格子到第j个格子的距离),不要使用曼哈顿距离
 粘粘自喜
2016-03-16 21:12
2楼
| ||||
|
加了估价函数后快如香港记者。。
| ||||
【题目描述】
在森林的深处，一场战争即将开始。像其他生物一样，猎豹们正在准备最后的战斗。他们不仅强壮，跑的比谁都快，他们还有一位智慧且勇敢的豹♂王（长者）。
长者知道仅凭强壮和速度是无法赢得战争的。他们需要完美的编队。现在有N只豹子，豹王编号为1，其他的豹子编号为2到N，现在这N只豹子站成了一行。豹王认为，最优的编队应该是所有的豹子按编号顺序从小到大（1..N)站成一行。豹王可以通过交换自己和其他豹子的位置对队列进行调整，但可以与豹王交换位置的豹子会随豹王位置的改变而改变。
设豹王的位置为i
如果（i%4==1） 豹王可以和(i+1), (i+3), (i+4), (i-4)位置上的豹子交换。
如果（i%4==2） 豹王可以和(i+1), (i-1), (i+4), (i-4)位置上的豹子交换。
如果（i%4==3） 豹王可以和(i+1), (i-1), (i+4), (i-4)位置上的豹子交换。
如果（i%4==0） 豹王可以和(i-3), (i-1), (i+4), (i-4)位置上的豹子交换。
可以与豹王交换的豹子的位置显然应该在1到N之间。
我们现在想知道最少要交换几次才能使编队最优
【输入格式】
多组数据。
每组数据的第一行为N（1<=N<=40,N保证为4的倍数）。
之后有N个整数，描述最初这N只豹子的排列顺序。
输入文件结尾有一个0；
【输出格式】
对于每组数据，输出最少的交换次数
【样例输入】
4 1 2 3 4 4 4 2 3 1 8 5 2 3 4 8 6 7 1 8 5 2 8 3 6 7 1 4 0
【样例输出】
0 1 2 7
【提示】