小米笔试 - 1012

BraumAce2024年10月13日约 1059 字大约 4 分钟

小米笔试 - 1012

宝石项链

题面

小明正在玩弄他的一串宝石项链。这个项链还没有封口，是一条链，初始的从左到右宝石分别编号 $1,2,3,...,n$ 。然而经过一段时间操作，小明觉得他应该把项链左右翻转一下了，将某个宝石调到其整条项链的前面或者后面去。小明在正式进行调整前，希望你能告诉他经过这个操作后宝石项链的样子。

输入描述：
第一行 $2$ 个空格隔开的整数 $n$ 和 $q$ ，表示宝石数量和操作次数。
第二行 $3q$ 个空格隔开的整数 $a_1, b_1, op_1, a_2, b_2, op_2,...,a_q, b_q, op_q$ ，对第 $i$ 次操作，表示将编号为 $a_i$ 的宝石取下，放到编号为 $b_i$ 的宝石旁边，如 $op_i = 0$ 时放到其前，否则放到其后。
$1≤n,q≤50000, 1≤a_i,b_i≤n, opi∈{0,1}$ 。保证 $a_i≠b_i$ 。

输出描述：
输出一行 $n$ 个整数，表示调整后，从左到右宝石的编号。

思路与代码：

使用双向链表来模拟项链的所有操作。

import java.util.*;

public class Main {
    static class Node {
        int val;
        Node prev, next;
        Node(int val) {
            this.val = val;
        }
    }

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int q = sc.nextInt();

        Node[] nodes = new Node[n + 1];
        Node head = new Node(0);
        Node tail = head;

        for (int i = 1; i <= n; i++) {
            Node node = new Node(i);
            nodes[i] = node;
            tail.next = node;
            node.prev = tail;
            tail = node;
        }

        for (int i = 0; i < q; i++) {
            int a = sc.nextInt();
            int b = sc.nextInt();
            int op = sc.nextInt();

            Node nodeA = nodes[a];
            Node nodeB = nodes[b];

            nodeA.prev.next = nodeA.next;
            if (nodeA.next != null) {
                nodeA.next.prev = nodeA.prev;
            }

            if (op == 0) {
                nodeA.prev = nodeB.prev;
                nodeA.next = nodeB;
                if (nodeB.prev != null) {
                    nodeB.prev.next = nodeA;
                } else {
                    head.next = nodeA;
                }
                nodeB.prev = nodeA;
            } else {
                nodeA.prev = nodeB;
                nodeA.next = nodeB.next;
                if (nodeB.next != null) {
                    nodeB.next.prev = nodeA;
                }
                nodeB.next = nodeA;
            }
        }

        int[] res = new int[n];
        Node cur = head.next;
        for (int i = 0; i < n; i++) {
            res[i] = cur.val;
            cur = cur.next;
        }

        for (int i = 0; i < n; i++) {
            System.out.print(res[i] + " ");
        }
    }
}

均衡

题面

小明在研究一个有趣的数组翻转操作问题，其中为了考虑均衡，他会同时翻转相邻两个数，他有一个长度为 $N$ 的数组 a，并可以进行任意次操作: 选择相邻的两个数，翻转这两个数的符号，即将 a[i] 和 a[i + 1] $(0<i<n-1)$ 的符号翻转。符号翻转的意思是正数变负数，负数变正数，在程序中即 $num = -num$ ，也即数学中的取相反数；当然 $0$ 翻转后还是 $0$ 。
小牛的任务是找到经过任意次数（可以为 $0$ 次）这些操作后，能够获得的最大数组和。当然，只要小明觉得有必要，同一个数也可以被反复选择。

输入描述：
第一行包含一个整数 $N$ ，表示数组的长度。
第二行包含 $N$ 个整数，a[1],a[2],…a[N]。 $(1<N<30000, -1000000000 < a[i] <10000000000)$

输出描述：
输出一个整数，表示经过任意次操作后数组的最大和。

示例：

输入：5
      1 -2 3 -4 5
输出：15

思路与代码：

有两种解法。

第一种，贪心，找结论：

只要有偶数个负数，则通过若干次操作一定能都变成正数。
只要有奇数个负数，则通过若干次操作一定变成，只有一个负数其他都是正数，因此贪心选个绝对值最小的数字当最后那个负数即可。

第二种，动态规划：

定义 DP 数组 dp[2][n]：
- dp[0][i] 表示 [i - 1, i] 这一对没有发生反转的前 $i$ 个数的最大和
- dp[1][i] 表示 [i - 1, i] 这一对有发生反转的前 $i$ 个数的最大和。
转移方程根据 dp[0][i - 1] 和 dp[1][i - 1] 分别来转移即可。

import java.util.*;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int[] a = new int[n];
        for (int i = 0; i < n; i++) {
            a[i] = sc.nextInt();
        }

        int[][] dp = new int[2][n];
        dp[0][0] = a[0];
        dp[1][0] = -a[0];
        if (n > 1) {
            dp[0][1] = a[0] + a[1];
            dp[1][1] = -a[0] - a[1];
        }

        for (int i = 2; i < n; i++) {
            dp[0][i] = Math.max(dp[0][i - 1] + a[i], dp[1][i - 1] + a[i]);
            dp[1][i] = Math.max(dp[0][i - 1] - a[i] - 2 * a[i - 1], dp[1][i - 1] + 2 * a[i - 1] - a[i]);
        }

        int res = Math.max(dp[0][n - 1], dp[1][n - 1]);

        System.out.println(res);
    }
}