筆試時(shí)間：2024年09月06日 秋招

歷史筆試傳送門：2023秋招筆試合集

第一題

題目

牛牛有一個(gè)由n個(gè)整數(shù)組成的數(shù)組[a1，a2，.,an]，他想將這n個(gè)數(shù)打亂后依次拼接，使得拼接得到的字符串字典序是所有拼接字符串中最小的。直接輸出這個(gè)打亂過后的數(shù)組。

輸入描述

第一行輸入一個(gè)整數(shù)n(1≤n≤10^5)代表數(shù)組中的元素?cái)?shù)量。

第二行輸入n個(gè)整數(shù)a1，a2，...,an(0≤ai≤10^9)代表數(shù)組元素。

輸出描述

在第一行上輸出n個(gè)整數(shù)，代表重新排列后的數(shù)組。

樣例輸入一

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(chǎn)和b，如果a + b < b + a，那么在最終的數(shù)組中，a一定在b的前面（否則我們調(diào)換a和b的位置字典序一定會(huì)變得更小）。因此，我們根據(jù)a + b < b + a進(jìn)行排序即可。

C++：[此代碼未進(jìn)行大量數(shù)據(jù)的測(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：[此代碼未進(jìn)行大量數(shù)據(jù)的測(cè)試，僅供參考]

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());
        }
        
        // 自定義排序規(guī)則
        Collections.sort(a, (x, y) -> {
            String s1 = Integer.toString(x);
            String s2 = Integer.toString(y);
            return (s1 + s2).compareTo(s2 + s1);
        });

        // 輸出結(jié)果
        for (int x : a) {
            System.out.print(x + " ");
        }
        System.out.println();
        
        sc.close();
    }
}

Python：[此代碼未進(jìn)行大量數(shù)據(jù)的測(cè)試，僅供參考]

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

# 自定義排序規(guī)則
a.sort(key=lambda x: str(x))

# 輸出結(jié)果
print(" ".join(map(str, a)))

第二題

題目

去哪兒會(huì)員體系分為大眾、白銀、黃金、鉑金和鉆石會(huì)員五個(gè)等級(jí)，等級(jí)由成長(zhǎng)值決定，成長(zhǎng)值越高，等級(jí)也就越高，也能夠享受更多的會(huì)員權(quán)益。這天，牛牛發(fā)現(xiàn)可以通過完成每日任務(wù)的方式快速獲得成長(zhǎng)值提升等級(jí)！一共有n個(gè)任務(wù)，每天都會(huì)解鎖一個(gè)新的任務(wù)，第i個(gè)任務(wù)達(dá)成后可以獲得ai點(diǎn)成長(zhǎng)值獎(jiǎng)勵(lì)。為了鼓勵(lì)用戶參與任務(wù)，在開始任務(wù)之前，還可以進(jìn)入“挑戰(zhàn)”模式，即預(yù)先設(shè)置自己能夠堅(jiān)持的天數(shù)x，在完成挑戰(zhàn)后，可以得到前張獎(jiǎng)勵(lì)翻倍卡，你可以自由選擇翻倍卡的使用順序，使得每一天的成長(zhǎng)值獎(jiǎng)勵(lì)翻倍，第i張翻倍卡可以將任務(wù)完成后的成長(zhǎng)值獎(jiǎng)勵(lì)乘以bi倍，例如：第一天任務(wù)獎(jiǎng)勵(lì)1點(diǎn)成長(zhǎng)值，第二天任務(wù)獎(jiǎng)勵(lì)2點(diǎn)成長(zhǎng)值，獎(jiǎng)勵(lì)一張四倍翻倍卡和一張兩倍翻倍卡，那么最少可以得到8點(diǎn)成長(zhǎng)值，最多可以得到10點(diǎn)成長(zhǎng)值。牛牛比較偷懶，他想要找到最少需要堅(jiān)持的天數(shù)，使得自己能夠獲得至少m點(diǎn)成長(zhǎng)值。

輸入描述

第一行輸入兩個(gè)整數(shù)n和m(1≤n≤10^5；1≤m≤10^12)代表任務(wù)總數(shù)量和需要的成長(zhǎng)值數(shù)量。

第二行n個(gè)整數(shù) a1,a2，..,an(0≤ai≤10^3)代表每一個(gè)任務(wù)獎(jiǎng)勵(lì)的成長(zhǎng)值點(diǎn)。

第三行n個(gè)整數(shù)b1,b2，..,bn(1≤bi≤10^3)代表按順字?jǐn)[放的翻倍卡的面值。

輸出描述

在一行輸出一個(gè)整數(shù)，代表最少堅(jiān)持的天數(shù)；若永遠(yuǎn)無(wú)法達(dá)到目標(biāo)，則直接輸出-1

樣例輸入一

5 20

1 2 3 4 5

4 2 3 5 10

樣例輸出一

3

樣例輸入二

2 20

1 2 

4 2 

樣例輸出二

-1

說明

牛?？梢蕴魬?zhàn)堅(jiān)持三天，在完成挑戰(zhàn)后他會(huì)獲得前三張翻倍卡。在第一個(gè)關(guān)卡使用面值為2的翻倍卡，獲得1×2=2金幣。在第二個(gè)關(guān)卡使用面值為3的翻倍卡，獲得2×3=6金幣。在第三個(gè)關(guān)卡使用面值為4的翻倍卡，獲得3×4=12金幣。由于2+6+12=20≥20，因此牛?？梢赃_(dá)成目標(biāo)?？梢宰C明更少的關(guān)卡無(wú)法滿足條件。注意，如果只計(jì)劃堅(jiān)持三天，則只能攜帶前3張翻倍卡。

參考題解

容易觀察到如果牛牛n天可以完成挑戰(zhàn)，那么n+1天,n+2天....都可以完成挑戰(zhàn)，因此我們二分天數(shù)，然后將前mid個(gè)任務(wù)根據(jù)成長(zhǎng)值排序，將前mid個(gè)翻倍卡根據(jù)倍數(shù)進(jìn)行排序，最后小的成長(zhǎng)值乘小的翻倍卡即可。

C++：[此代碼未進(jìn)行大量數(shù)據(jù)的測(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] =