笔试时间：2023年9月18日 秋招

第一题

题目：小红吃果子

有n棵树，每棵树的高度为ai，每棵树在bi的高度上有一个果子。小红从第一棵树的0高度位置开始，每次可以进行如下操作：

1、可以调整自身的高度，即从高度变为高度x + 1 或 x - 1，需要保证调整后高度仍然在0到ai之间；

2、或者从第棵树的高度移动到第i + 1棵树的高度，需要保证 x< ai+1；

小红始终不能超过所在树的高度，小红吃到所有果子，最少需要几次操作？

输入描述

第一行一个整数n，表示树的数量；

第二行n个整数ai，表示每棵树的高度；

第三行n个整数bi，表示每棵树上果子的高度。

1 <= n <= 10^5

1 <= bi <= ai < 10^9

输出描述

输出一个整数，表示最少需要的操作次数。

样例输入

5

3 4 5 6 7

1 2 3 4 5

样例输出

9

参考题解

贪心，直接上树和下树即可。

Java：[此代码未进行大量数据的测试，仅供参考]

import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int n = scanner.nextInt();
        int[] a = new int[n];

        for (int i = 0; i < n; i++) {
            a[i] = scanner.nextInt();
        }

        for (int i = 0; i < n; i++) {
            a[i] = scanner.nextInt();
        }

        long ans = n - 1 + a[0];
        for (int i = 0; i < n - 1; i++) {
            ans += Math.abs(a[i + 1] - a[i]);
        }

        System.out.println(ans);
    }
}

第二题

题目：小红做游戏

小红在和朋友们做游戏，包括小红一共n个人，大家围成了一个圈。第i个位置的人只记住了在他右手边的两个人，也就是说，位置1的人记住了位置2和位置3的人，位置n - 1的人记住了位置n和位置1的人。现在小红想知道，能不能还原出每个人的位置，如果有多种可能，任意输出一种即可，保证至少存在一种符合要求的情况。

输入描述

输入描述一行一个整数n，表示人数。

接下来n行，每行两个整数ai和bi，表示第i个人记住了第ai个人和第bi个人。 (bi不一定在ai的右边)。

3 <= n <= 10^5

1 <= ai, bi <= n

输出描述

还原出每个人的位置，输出一行n个整数，表示每个人的位置。

样例输入

5

2 3

4 3

4 5

1 5

2 1

样例输出

1 2 3 4 5

参考题解

Java：[此代码未进行大量数据的测试，仅供参考]

import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int N = 100004;
        int[] a = new int[N];
        int[] b = new int[N];
        int n = scanner.nextInt();
        int[] z = new int[N];

        for (int i = 1; i <= n; i++) {
            a[i] = scanner.nextInt();
            b[i] = scanner.nextInt();
        }

        z[1] = 1;
        z[2] = a[1];
        z[3] = b[1];

        if (!ok(n, a, b, z)) {
            z[2] = b[1];
            z[3] = a[1];
            ok(n, a, b, z);