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();
    }
}