笔试时间：2024年04月07日

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

第一题

题目：小苯送礼物

小苯是“小红书app”的一名博主,这天他想要给自己的“铁粉”送一些礼物。他有n名粉丝，编号从1到n,但他只能选择其中k名送礼物,他决定选择其中对他支持力度最大的前k名粉丝。(如果两名支持力度相同,则优先选择收藏数更多的,如果都一样,则优先选择编号更小的(因为这意味着他关注小苯的时间更早))具体的:每名粉丝如果每给小苯点一次赞,则他对小苯就增加了1点支持力度,如果他每收藏小苯的一篇文章,则他对小苯增加2点支持力度。现在小苯想知道,他应该选择哪k名粉丝送出礼物,请你帮帮他吧。

输入描述

输入包括n+1行

第一行两个正整数n, k分别表示对小苯有过支持的粉丝个数，以及小苯选择送礼的粉丝个数。

接下来n行,每行两个整数x, y,表示第i位粉丝给小苯点过×次赞,收藏过y个小苯的文章。

输出描述

输出包含一行k个正整数,表示小苯选择出送礼物的粉丝们的编号。(按照升序输出)。

样例输入

4 2

1 2

2 1

3 0

1 3

样例输出

1 4

参考题解

模拟排序即可。

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

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

int main () {
  int n, k; cin >> n >> k;
  vector<vector<int>> a(n);
  for (int i = 0; i < n; ++i) {
    int x, y; cin >> x >> y;
    a[i] = {i, x, y};
  }
  sort(a.begin(), a.end(), [&](auto& b, auto& c) {
    int s1 = b[1] + 2 * b[2], s2 = c[1] + 2 * c[2];
    if (s1 == s2) {
      return b[2] == c[2] ? b[0] < c[0] : b[2] > c[2];
    }
    return s1 > s2;
  });
  vector<int> ans(k);
  for (int i = 0; i < k; ++i) ans[i] = a[i][0] + 1;
  sort(ans.begin(), ans.end());
  for (int e : ans) cout << e << " ";
}

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

import java.util.*;

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

        for (int i = 0; i < n; i++) {
            int x = scanner.nextInt();
            int y = scanner.nextInt();
            a.add(new int[]{i, x, y});
        }

        a.sort((b, c) -> {
            int s1 = b[1] + 2 * b[2];
            int s2 = c[1] + 2 * c[2];
            if (s1 == s2) {
                return b[2] == c[2] ? Integer.compare(b[0], c[0]) : Integer.compare(c[2], b[2]);
            }
            return Integer.compare(s2, s1);
        });

        List<Integer> ans = new ArrayList<>();
        for (int i = 0; i < k; i++) {
            ans.add(a.get(i)[0] + 1);
        }
        Collections.sort(ans);
        for (int e : ans) {
            System.out.print(e + " ");
        }
    }
}

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

n, k = map(int, input().split())
a = []

for i in range(n):
    x, y = map(int, input().split())
    a.append([i, x, y])

a.sort(key=lambda b: (b[1] + 2 * b[2], -b[2], b[0]), reverse=True)

ans = [a[i][0] + 1 for i in range(k)]
ans.sort()

print(" ".join(map(str, ans)))

第二题

题目：小红的精选笔记

小红在小红书上面发布了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 <algorithm>
#include <queue>
using namespace std;
using ll = long long;
int main () {
  int n, k; cin >> n >> k;
  vector<vector<int>> a(n, vector<int>(2));
  for (int i = 0; i < n; ++i) cin >> a[i][0];
  for (int i = 0; i < n; ++i) cin >> a[i][1];
  sort(a.begin(), a.end(), [&](auto& b, auto& c) {
    return b[1] > c[1];
  });
  priority_queue<int, vector<int>, greater<int>> pq;
  ll ans = 0, sum = 0;
  for (int i = 0; i < n; ++i) {
    pq.push(a[i][0]);
    sum += a[i][0];
    if (i >= k - 1) {
      ans = max(ans, sum * a[i][1]);
      sum -= pq.top(); pq.pop();
    }
  }
  cout << ans;
}

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

import java.util.*;

public class Main {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(