笔试时间：2023年4月10日 春招实习

备注：第三题暂无有题解

第一题

题目：小红拆分数组

小红拿到了一个长度为n的数组，她希望把该数组拆分成k个非空子序列。(每个元素必须出现在某个子序列中,且恰好出现一次),使得这个k子序列的平均数之和尽可能小。你能帮帮她吗？

注：子序列可以不连续。例如数组为[3,2,1,3],k=2时,子序列可以拆分为[3,1]和[2,3]

输入描述

第一行输入两个正整数n和k，代表数组的长度、子序列的数量；

第二行输入个n正整数,代表数组的元素ai；

1≤k≤n≤10^5

-10^9≤a ≤10^9

输出描述

一个小数,代表最终平均数之和的最小值。如果你的答案和正确答案的误差不超过10^-6，则认为答案正确。

样例输入

4 3

-1 2 -1 3

样例输出

0.50000000000

提示：

拆分为以下3个子序列:[-1] [2,3] [-1]

平均数之和为(-1)+2.5+(-1)=0.5

参考题解

贪心的思想。

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

n, k = map(int, input().split())
a = list(map(int, input().split()))
a.sort()
ans = sum(a[:k-1])
sum_ = sum(a[k-1:])
ans += sum_ / (n - k + 1)
print(ans)

第二题

题目：RED字符串

给定一个整数x，请你构造一个仅由'r'、'e'、d'三种字符组成的字符串，其中回文子串的数量恰好为x。字符串的长度不得超过10^5。

输入描述

一个正整数x。

1<=x<=10^9

输出描述

输出一个仅由'r','e','d' 三种字符组成的字符串。若有多解输出任意即可。

样例输入

3

样例输出

red

参考题解

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

import java.util.HashMap;
import java.util.Map;
import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        long x = scanner.nextLong(); 

        Map<Long, Long> myMap = new HashMap<>();
        myMap.put(1L, 1L);
        myMap.put(10L, 55L);
        myMap.put(100L, 5050L);
        myMap.put(1000L, 500500L);
        myMap.put(10000L, 50005000L);
        my