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

第一题

题目：小A的宝石

小A收集到了n颗宝石，第i个宝石有其美丽值a[i]，小A决定挑出一些宝石带回家，一颗带回家的宝石给小A带来的快乐值与其石头本身的美丽值相等。虽然并不是所有宝石的美丽值都为正数，但是小A还是认为能有收获也是一件很开心的事，故而每带回家3颗宝石，小A的快乐值就会加k。问小A要如何选择宝石带回家，使得自已能获得的快乐值最高。请输出快乐值的最大值。

输入描述

第一行包括两个正整数n,k，表示收集到的宝石的数量和每带回家3颗宝石快乐值的增加量。

第二行包括n个整数，表示i第宝石的美丽值。

-1000 <= a[i] <= 1000, 1 <= k <= 1000,1 <= n <= 100000。

输出描述

输出能获得的快乐值的最大值。

样例输入

5 5

1 2 3 4 -6

样例输出

15

提示

带回前三颗宝石能获得(1+2+3+5=11)的快乐值，同时再带回第四颗宝石，总共获得的快乐值为15，这时是能获得的最大的快乐值。

参考题解

贪心算法，对宝石进行倒序排列，假设排序后的前缀和为s[i]，则最后的结果为max(s[i] + i/3 * k)。

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

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

using namespace std;

int main() {
    int n, k;
    cin >> n >> k;
    vector<int> a(n);
    for (int i = 0; i < n; i++) {
        cin >> a[i];
    }
    sort(a.begin(), a.end(), greater<int>());
    int ans = 0;
    int s = 0;
    for (int i = 0; i < n; i++) {
        s += a[i];
        ans = max(ans, s + (i + 1) / 3 * k);
    }
    cout << ans << endl;
    return 0;
}

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

import java.util.Arrays;
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();
        int[] a = new int[n];