今天早上参加了字节跳动的笔试。

4 道题，做出 3 题，遗憾的是不会做的那一题我甚至不知道他考察的算法是什么，以前至少还知道，哦，这是计算几何，我不会，这是动态规划，我写不出来，这次干脆连题目都不知道问的是什么了。
剩下 3 题都比较简单。

第 1 题，找零。

由于货币是 1、4、16、64 成倍数关系，所以贪心成立。

10:04，1 次直接 AC。

import java.util.Scanner;

public class Main {

    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        int n = in.nextInt();
        int x = 1024 - n;
        int ans = 0;
        int[] a = {1, 4, 16, 64};
        for (int i = a.length - 1; i >= 0;i--) {
            ans += x / a[i];
            x %= a[i];
        }
        System.out.println(ans);
        in.close();
    }
}

第 2 题，万万没想到之聪明的编辑。

字符串的处理，估计是考查代码能力的，是不是能够足够细心把一步步操作写清楚。

首先从题意可以知道，连续 3 个同样的字母，就消去 1 个，变成 2 个。

并且，显然可以知道，如果有连续 $n$ 个同样的字母，$n \geqslant 3$，那么最终会变成 2 个该字母，例如 wooooooow 中间有 7 个 o，每连续 3 个同样的字母连在一起就去掉一个，那么若干次操作以后会直接变成 oo。

所以，第 1 条规则的化简，就是，如果存在连续 $n$ 个相同的字母，则削减为 2 个。

第 2 条规则，由于说了是从左往右执行的，所以直接模拟。

经过了第 1 条规则的处理以后，剩下的字符串要么是由不同的单字母组成，最多同一个字母连续出现 2 次，从左往右遍历，看是不是存在 AABB 的格式，模拟处理。

难度可能是在于，删除字母以后，字符数组需要将右边的字符左移以填补删除的空位，或者需要构造新的字符串对象，这个操作很容易出错，必须特别小心。

如果用正则表达式来写就非常简单了，这 2 条规则对应的 RegEx 分别是 ("([a-z])\\1{2,}", "$1$1") 和 ("([a-z])\\1{1}([a-z])\\2{1}", "$1$1$2")，很简单，不解释。

10:19，1 次直接 AC。

import java.util.Scanner;

public class Main {

    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        int n = in.nextInt();
        for (int i = 0; i < n; i++) {
            String s = in.next();
            s = s.replaceAll("([a-z])\\1{2,}", "$1$1");
            s = s.replaceAll("([a-z])\\1{1}([a-z])\\2{1}", "$1$1$2");
            System.out.println(s);
        }
        in.close();
    }
}

第 3 题，奖品分配。

有点难，一下子没有读懂题目意思，所以先做了第 4 题。

第 4 题，剪绳子。

除了样例，还需要注意以下 3 种情况：

• 5 根绳子，分别为 1、2、6、8、9，需要 3 段等长的，显然是 3 段长度为 6 的，似乎是排序以后倒着贪心？
• 5 根绳子，分别为 1、2、3、4、100，需要 2 段等长的，显然是将 100 分为 2 段 50，所以排序不可能了，贪心也不成立。
• 5 根绳子，分别为 1、2、3、50、100，需要 3 段等长的，显然是将 100 分为 2 段 50，加上已经有的那段 50，而不是尝试 100 三等分。

综上，这题既不是贪心（况且贪心已经考过一题了），也不太会是动态规划。

这题的决胜关键在于，花多长时间思考才能意识到这题是二分答案，如果能意识到，那么二分搜索的部分没有任何难度。

左端点是 0，因为显然每一段的长度必须大于 0，右端点是最长的那根绳子，因为不管怎么分，不管分多少段（哪怕是 1 段），都不可能比最长的甚至还长。

二分中点就是期望的裁剪后的长度 $mid$，用这个长度 $mid$ 去算每一根绳子如果切成 $mid$ 长度能够切成多少段，然后加起来。所有段数相加，和目标需要的段数比较。

由于二分中点是浮点数，所以除法结果向下取整计算段数。

• 如果切出来的段数大于目标段数，说明切得太细了，那么左端点变成 $mid$，尝试加大切割长度。
• 如果切出来的段数小于目标段数，说明要减小切割长度，右端点左移。
• 如果切出来的段数等于目标段数，由于题目要求长度尽可能长，所以等效于要加大切割长度，左端点右移。

10:43，1 次直接 AC。

import java.util.Scanner;

public class Main {

    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        int n = in.nextInt();
        int m = in.nextInt();
        int[] a = new int[n];
        double left = 0;
        int right = 0;
        for (int i = 0; i < n; i++) {
            a[i] = in.nextInt();
            if (a[i] > right) {
                right = a[i];
            }
        }
        double ans = binarySearch(a, left, right, m);
        System.out.printf("%.2f", ans);
        in.close();
    }

    private static double binarySearch(int[] a, double left, double right, int target) {
        while (Math.abs(left - right) > 1E-6) {
            double mid = (left + right) / 2;
            int count = 0;
            for (int x : a) {
                count += (int)(x / mid);
            }
            if (count < target) {
                right = mid;
            } else if (count >= target) {
                left = mid;
            }
        }
        return left;
    }
}

还有 80 分钟，回过头做第 3 题。

首先，理解题目意思花了 30 分钟，到 11:10 左右我才看懂第 2 组样例的那个 8 是怎么回事。

然后开始思考到底这题是考查什么东西。

到了大概 11:20 多，接近 11:30 的时候，弹出一个系统消息，说，第 3 题增加了样例的解释，已更新题目，请刷新页面查看。

我刷新了，然后看到题目下面多了这一句话。

垃圾出题人，害我白花 30 分钟去想那个 “比左右高” 到底是什么意思。

然后还剩 30 分钟，却完全不知道这题考的是什么。

随手糊一个算法上去，通过了 11.11% 的测试数据，剩下的超时。

不管了。

后来问了 zerol，他给出的第 1 个思路是，往图论上面转化。

看成有向图。一个必须比另一个大就连边。想想是不是无环的。如果是那就 DAG 上 DP，可以按拓扑序计算答案（或者记忆化搜索），没出度是 1 否则是 max 后继节点 +1。

后来进一步思考，zerol 给出了简单做法：

所有数字从小到大排，按这个顺序贪心填。其实就是一种拓扑序，注意相同数字相邻的情况。就按一定顺序填，数字从小到大，一批一批填。