2021秋招-招银网络-提前批-洗牌算法题

描述

第三道算法题:洗牌

将一堆牌平均分成两堆(如果牌数是奇数,则左手比右手多一张),然后先放右手最下面的一张牌,然后放左手最后一张牌,依次类推。然后再洗。

输入: n表示有n张牌,k表示洗k次,然后再跟上牌的序号。
输出:洗完牌后的序列(使用空格分开)

测试用例:7 2 1 2 3 4 5 6 7 // 表示有1 2 3 4 5 6 7 这7张牌,要洗2次。

初始:1 2 3 4 || 5 6 7

第一轮:1 2 5 3 || 6 4 7

第二轮:1 6 2 4 5 7 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

package cn.eilene.cmbchina;

import java.util.Scanner;


/**
* @Description 洗牌
* @Author MY-HE
* @Date 2020-06-23 15:01
*/
public class Problem03 {
int n, k;
int[] c;

public void solution() {
// p、q 用来记录上边一堆
// r、s 用来记录下边一堆
int p = 0;
int q = n % 2 == 0 ? n / 2 - 1 : n / 2;
int r = q + 1;
int s = n - 1;

// 洗牌次数
int m = 1;
while (m <= k) {
// 根据第几次洗牌来记录插入顺序
int e, f, g, h;
int[] d = new int[n];
// 奇数次洗牌
if (m % 2 == 1) {
e = p;
f = q;
g = r;
h = s;
} else {
// 偶数次洗牌
e = r;
f = s;
g = p;
h = q;
}
for (int i = d.length - 1; i >= 0; i--) {
if (h >= g && f >= e) {
// 交叉插入
d[i] = i % 2 == 0 ? c[h--] : c[f--];
} else {
if (h >= g)
d[i] = c[h--];
else
d[i] = c[f--];
}
}
System.arraycopy(d, 0, c, 0, d.length);
m++;
}
for (int i = 0; i < c.length; i++) {
if (i < c.length - 1) {
System.out.print(c[i] + " ");
} else {
System.out.println(c[i]);
}
}
}

public static void main(String[] args) {
Problem03 p3 = new Problem03();
Scanner sc = new Scanner(System.in);
p3.n = sc.nextInt();
p3.k = sc.nextInt();
int i = 0;
p3.c = new int[p3.n];

while (sc.hasNextInt()) {
p3.c[i++] = sc.nextInt();
}
p3.solution();
}
}