笔试时间：2023年9月15日 秋招

备注：第五题暂无题解

第一题

题目：牛妹的数链们

牛妹有一堆数链，这些数链里面的数字都杂乱无章，牛妹想整理一下这些数字，把它们从小到大排成一个数链。

样例输入

[{1,3,5},{2,4,6},{1,2,3,4,5,6}]

样例输出

{1,1,2,2,3,3,4,4,5,5,6,6}

参考题解

暴力，数组排序，然后转化成链表

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

class ListNode:
    def __init__(self, val=0, next=None):
        self.val = val
        self.next = next

def merge_linked_lists(lists):
    merged_data = []

    for linked_list in lists:
        current = linked_list
        while current:
            merged_data.append(current.val)
            current = current.next

    sorted_data = sorted(merged_data)

    dummy = ListNode()
    current = dummy

    for val in sorted_data:
        current.next = ListNode(val)
        current = current.next
    return dummy.next

# 合并数链并返回排序后的链表
result = merge_linked_lists(data)

# 打印排序后的链表
while result:
    print(result.val, end=" ")
    result = result.next

第二题

题目：小Q的奇偶操作数组

小Q有一个长度为n的数组，它对这个数组有k次操作机会，操作如下：可以选择数组中的任意一个数字并改变它。

1、如果选择的数字x是奇数，那么这个奇数乘以2，即x = a * 2；

2、如果选择的数字x是偶数，那么这个偶数乘以2再加1，即x = a * 2 +1；

小Q想让这k次操作之后，数组元素之和最小，请你输出这个最小值是多少?

保证最终的元素之和不超过10^18。

输入描述

第一行两个正整数n和k，用空格隔开。

第二行输入n个正整数ai，每个ai代表数组的第i个元素。

1 <= n <= 200000

1 <= k <= 200000

1 <= ai <= 10000000

输出描述

输出一个整数，代表k次操作之后，数组元素之和的最小值。

样例输入

5 3

1 2 3 5 2

样例输出

20

提示:其中一种方案是:

1、将第一个元素: 1=>2

2、将第一个元素: 2=>5

3、将第二个元素:2=>5

总共3次操作，最后元素为5 5 3 5 2，数组元素之和为20

参考题解

贪心，使用小顶堆排序，每次取出最小元素即可。

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

#include <iostream>
#include <queue>

using namespace std;

typedef long long ll;

int main() {
    int n, k, x;
    priority_queue<ll, vector<ll>, greater<ll>> minHeap;  

    // 输入 n 和 k
    cin >> n >> k;

    for (int i = 0; i < n; i++) { 
        cin >> x;
        minHeap.push(x);
    }

    for (int i = 0; i < k; i++) {
        ll smallest = minHeap.top();
        minHeap.pop();
        ll newElement = (smallest & 1) ? (smallest << 1) : (smallest << 1 | 1);
        minHeap.push(newElement);
    }

    ll ans = 0;

    while (!minHeap.empty()) {
        ans += minHeap.top();
        minHeap.pop();
    }

    cout << ans << endl;
    return 0;
}

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

import java.util.PriorityQueue;
import java.util.Scanner;

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

        for (int i = 0; i < n; i++) {
            int x = scanner.nextInt();
            minHeap.add((long) x);
        }

        for (int i = 0; i < k; i++) {
            long smallest = minHeap.poll();
            long newElement = (smallest & 1) == 1 ? smallest << 1 : (smallest << 1) | 1;
            minHeap.add(newElement);
        }

        long ans = 0;

        while (!minHeap.isEmpty()) {
            ans += minHeap.poll();
        }

        System.out.println(ans);
    }
}

Python：[