笔试时间：2024年05月10日

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

第一题

题目：小红的碾压墙

小红是游戏《H炉》的一个主播。她经常去小红书发布关于H炉的卡牌研究攻略。H炉有一张牌叫做碾压墙，可以消灭敌方最左边和最右边的随从，另一张牌叫做致命射击，可以随机消灭一个敌方随从。如果小红使用两张致命射击恰好消灭了敌方最左边和最右边的随从（恰好造成了一张碾压墙的效果），就会有人在评论区发布“碾压墙” 。注意：两张致命射击的结算有先后顺序，即两张致命射击不会消灭同一个敌方随从。现在有 n 个敌方随从，小红想知道她使用两张致命射击后，恰好造成一张碾压墙的效果的概率是多少。你的答案请四舍五入保留10位小数。

输入描述

第一行输入一个整数 n(2 ≤ n ≤ 106) 。

输出描述

输出一个实数表示答案(请四舍五入保留10位小数)。

样例输入一

2

样例输出一

1.0000000000

说明只有两个随从，必然造成碾压墙的效果。

样例输入二

3

样例输出二

0.3333333333

参考题解

第一次选取头或者尾的概率为2/n，第二次选取剩余的头尾部分是1/(n-1)，二者相乘即可。

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

#include <iostream>
#include <iomanip>

int main() {
    int n;
    std::cin >> n;
    // 保留10位小数
    std::cout << std::fixed << std::setprecision(10) << (2.0 / n * 1.0 / (n - 1)) << std::endl;
    return 0;
}

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

import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int n = scanner.nextInt();
        // 保留10位小数
        System.out.printf("%.10f\n", (2.0 / n * 1.0 / (n - 1)));
        scanner.close();
    }
}

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

n = int(input())
#保留10位小数
print('%.10f' % (2/n * 1/(n-1)))

第二题

题目：小红的精选笔记

小红在小红书上面发布了n篇笔记，其中第i筒笔记的点赞数量为ai,评论数为bi,。现在小红准备选择k筒笔记作为“精选笔记合集”，合集的优秀程度为:所有笔记点赞数之和乘以评论数的最小值。 现在小红想知道，最终台集最大的优秀度是多少？

输入描述

第一行输入两个正整数n,k,代表笔记的数量,以及小红准备选择的合集大小。

第二行输入n个正整教ai,代表每简笔记的点赞数。

第三行输入n个正整数bi,代表每篇笔记的评论数。

输出描述

—个正整数,代表最终最大的优秀度。

样例输入

4 2

1 2 3 4

3 4 2 1

样例输出

10

提示：选第二篇和第三篇即可。

参考题解

比较简单：按照评论数排序，考虑每个评论数作为最小评论数，统计大于当前评论数的笔记中最大的k个点赞数之和，这一步可以用优先队列实现。

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

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

using namespace std;

int main() {
    int n, k;
    cin >> n >> k;
    vector<int> A(n), B(n);
    for (int i = 0; i < n; i++) {
        cin >> A[i];
    }
    for (int i = 0; i < n; i++) {
        cin >> B[i];
    }

    vector<pair<int, int>> notes(n);
    for (int i = 0; i < n; i++) {
        notes[i] = {A[i], B[i]};
    }

    sort(notes.begin(), notes.end(), [](pair<int, int>& a, pair<int, int>& b) {
        return b.second < a.second;
    });

    priority_queue<int, vector<int>, greater<int>> h; // 小顶堆
    long long sum = 0;
    long long res = 0;

    for (int i = 0; i < n; i++) {
        if (h.size() < k) {
            h.push(notes[i].first);
            sum += notes[i].first;
        } else {
            if (h.top() <