笔试时间：2024年09月06日 秋招

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

第一题

题目

牛牛有一个由n个整数组成的数组[a1，a2，.,an]，他想将这n个数打乱后依次拼接，使得拼接得到的字符串字典序是所有拼接字符串中最小的。直接输出这个打乱过后的数组。

输入描述

第一行输入一个整数n(1≤n≤10^5)代表数组中的元素数量。

第二行输入n个整数a1，a2，...,an(0≤ai≤10^9)代表数组元素。

输出描述

在第一行上输出n个整数，代表重新排列后的数组。

样例输入一

3

2 1 -1

样例输出一

-1 1 2

说明

一共有2 1 -1、2 -1 1、1 2 -1、1 -1 2、-1 2 1和-1 1 2六种字符串，其中-1 1 2是字典序最小的。

样例输入二

3

2 1 21

样例输出二

1 21 2

参考题解

给定字符串a和b，如果a + b < b + a，那么在最终的数组中，a一定在b的前面（否则我们调换a和b的位置字典序一定会变得更小）。因此，我们根据a + b < b + a进行排序即可。

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

#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;
int main() {
    int n;
    cin >> n;
    vector<int> a(n);
    for (int i = 0; i < n; i++) {
        cin >> a[i];
    }

    sort(a.begin(), a.end(), [&](int x, int y) -> bool {
        string s1 = to_string(x);
        string s2 = to_string(y);
        return s1 + s2 < s2 + s1;
    });

    for (int x : a) {
        cout << x << " ";
    }
    cout << "\n";
}

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

import java.util.*;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        List<Integer> a = new ArrayList<>();
        
        for (int i = 0; i < n; i++) {
            a.add(sc.nextInt());
        }
        
        // 自定义排序规则
        Collections.sort(a, (x, y) -> {
            String s1 = Integer.toString(x);
            String s2 = Integer.toString(y);
            return (s1 + s2).compareTo(s2 + s1);
        });

        // 输出结果
        for (int x : a) {
            System.out.print(x + " ");
        }
        System.out.println();
        
        sc.close();
    }
}

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

n = int(input())
a = list(map(int, input().split()))

# 自定义排序规则
a.sort(key=lambda x: str(x))

# 输出结果
print(" ".join(map(str, a)))

第二题

题目

去哪儿会员体系分为大众、白银、黄金、铂金和钻石会员五个等级，等级由成长值决定，成长值越高，等级也就越高，也能够享受更多的会员权益。这天，牛牛发现可以通过完成每日任务的方式快速获得成长值提升等级！一共有n个任务，每天都会解锁一个新的任务，第i个任务达成后可以获得ai点成长值奖励。为了鼓励用户参与任务，在开始任务之前，还可以进入“挑战”模式，即预先设置自己能够坚持的天数x，在完成挑战后，可以得到前张奖励翻倍卡，你可以自由选择翻倍卡的使用顺序，使得每一天的成长值奖励翻倍，第i张翻倍卡可以将任务完成后的成长值奖励乘以bi倍，例如：第一天任务奖励1点成长值，第二天任务奖励2点成长值，奖励一张四倍翻倍卡和一张两倍翻倍卡，那么最少可以得到8点成长值，最多可以得到10点成长值。牛牛比较偷懒，他想要找到最少需要坚持的天数，使得自己能够获得至少m点成长值。

输入描述

第一行输入两个整数n和m(1≤n≤10^5；1≤m≤10^12)代表任务总数量和需要的成长值数量。

第二行n个整数 a1,a2，..,an(0≤ai≤10^3)代表每一个任务奖励的成长值点。

第三行n个整数b1,b2，..,bn(1≤bi≤10^3)代表按顺字摆放的翻倍卡的面值。

输出描述

在一行输出一个整数，代表最少坚持的天数；若永远无法达到目标，则直接输出-1

样例输入一

5 20

1 2 3 4 5

4 2 3 5 10

样例输出一

3

样例输入二

2 20

1 2 

4 2 

样例输出二

-1

说明

牛牛可以挑战坚持三天，在完成挑战后他会获得前三张翻倍卡。在第一个关卡使用面值为2的翻倍卡，获得1×2=2金币。在第二个关卡使用面值为3的翻倍卡，获得2×3=6金币。在第三个关卡使用面值为4的翻倍卡，获得3×4=12金币。由于2+6+12=20≥20，因此牛牛可以达成目标。可以证明更少的关卡无法满足条件。注意，如果只计划坚持三天，则只能携带前3张翻倍卡。

参考题解

容易观察到如果牛牛n天可以完成挑战，那么n+1天,n+2天....都可以完成挑战，因此我们二分天数，然后将前mid个任务根据成长值排序，将前mid个翻倍卡根据倍数进行排序，最后小的成长值乘小的翻倍卡即可。

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

#include<iostream>
#include<vector>
using namespace std;
#define ll long long
int main() {
    int n;
    cin >> n;
    ll m;
    cin >> m;
    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];
    }

    int l = 1, r = n + 1;
    while (l < r) {
        int mid = (l + r) >> 1;
        vector<int> c(mid), d(mid);
        for (int i = 0; i < mid; i++) {
            c[i] = a[i];
            d[i] =