笔试时间：2024年05月08日

历史笔试传送门：2023秋招笔试合集

第一题

题目

有n个自爆怪，每只怪物血量为ai，并且怪物死亡时(血量小于等于0)会发生自爆，对其他怪物造成等同于其初始血量的伤害。小杰每次攻击可以对任意一只怪物造成1点伤害。她想知道，最少攻击多少次可以击杀全部怪物？

输入描述

第一行输入一个正整数n，代表怪物的数量

第二行输入n个正整数ai，代表每只怪物的血量。1< n <10^5, 1< ai < 10^9。

输出描述

一个正整数，代表小杰的最小攻击次数。

样例输入

3

1 2 3

样例输出

2

说明

对第1只怪物、第2只怪物名攻击次即可。攻击第1只怪物时，第1只怪物死亡时白爆，对第 2、3 只怪物备造成1点伤害。此时第2只怪物血量只剩1点，再攻击一次即可。然后第2只怪物自爆，对第3只怪物造成2点伤害，第3 只怪物也死亡。

参考题解

优先攻击血量小的怪物，使得它们死亡时能对其他血量较高的怪物造成伤害。如果当前累计造成的伤害点小于当前怪物的血量，那么需要额外进行（ 血量-伤害点）次攻击，以确保这只怪物死亡。额外的攻击次数被累加到最终结果中。每次怪物死亡时（无论是通过攻击还是其他怪物的自爆），它都会对剩余的怪物造成等同于其血量的伤害。因此，更新累计造成的伤害 ，即将当前怪物的血量加上。

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

#include <iostream>
#include <queue>
#include <vector>

int main() {
    std::priority_queue<int, std::vector<int>, std::greater<int>> q; // 最小堆
    int n;
    std::cin >> n;
    
    for (int i = 0; i < n; i++) {
        int t;
        std::cin >> t;
        q.push(t); // 向优先队列中添加元素
    }
    
    int res = 0;
    int s = 0;
    while (!q.empty()) {
        int x = q.top(); // 取出队首元素
        q.pop(); // 移除队首元素
        if (s < x) {
            res += x - s;
        }
        s += x;
    }
    
    std::cout << res << std::endl;
    return 0;
}

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

public class Main {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int n = scanner.nextInt();
        // 创建一个优先队列，自然排序实现最小堆
        PriorityQueue<Integer> q = new PriorityQueue<>();
        for (int i = 0; i < n; i++) {
            int t = scanner.nextInt();
            q.offer(t); // 向优先队列中添加元素
        }
        int res = 0;
        int s = 0;
        while (!q.isEmpty()) {
            int x = q.poll(); // 从优先队列中取出并移除队首元素
            if (s < x) {
                res += x - s;
            }
            s += x;
        }
        System.out.println(res);
    }
}

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

import heapq

def main():
    q = []
    n = int(input())
    
    for _ in range(n):
        t = int(input())
        heapq.heappush(q, t) # 向优先队列中添加元素
    
    res = 0
    s = 0
    while q:
        x = heapq.heappop(q) # 取出并移除队首元素
        if s < x:
            res += x - s
        s += x
    
    print(res)

if __name__ == "__main__":
    main()

第二题

题目

小杰有一个长为n的排列p，但大白熊将其隐藏了起来。现在大白熊给了小杰一个长度为n-1的数组a，其中ai = pi + pi+1 小杰想用数组a还原出排列p来，你能帮帮她吗？

输入描述

输入包含两行。

第一行一个正整数n(1≤n≤ 2 x 10^3^)，表示排列p 的长度。

第二行n-1个正整数a~i~(1<a~i~<n+(n-1))，表示题中所述数组a的元素。

输出描述

输出包含一行n个数字，表示还原出来的排列p。如果有多解，请输出字典序最小的解，但如果无解，请输出 -1。

样例输入

4 5 7 5

样例输出

1 4 3 2

参考题解

要从给定的输入数组 中推导出 p 的可能值。但由于 p 是一个排列，尝试从 1 到 n 的所有可能的首元素开始，尝试构建整个排列 p 并验证它是否满足条件。要求字典序最小，所以从1开始，设置两个数组，一个为输入的数组，一个数组第一个为1，剩余元素由输入数组作差得到。以此类推，最后得到符合的排列。

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

#include <iostream>
#include <vector>
#include <unordered_set>

int main() {
    int n;
    std::cin >> n;
    std::vector<int> a(n);

    for (int i = 1; i < n; ++i) {
        std::cin >> a[i];
    }

    for (int i = 1; i < n; ++i) {
        std::vector<int> t(n);
        t[0] = 1;
        std::unordered_set<int> map;
        map.insert(t[0]);

        for (int j = 1; j < n; ++j) {
            t[j] = a[j] - t[j - 1];
            if (t[j] > n || t[j] <= 0) break;
            map.insert(t[j]);
        }

        if (map.size() == n) {
            for (int num : t) {
                std::cout << num << " ";
            }
            std::cout << std::endl;
            return 0;
        }
    }
    std::cout << "-1" << std::endl;
    return 0;
}

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

public class Main {
    public static void main(String[] args) {

        Scanner scanner = new Scanner(System.in);
        int n = scanner.nextInt();
        int[] a = new int[n];