首页 > 科大讯飞 2022届 秋招 测试类 笔试 填空题 编程题
头像
牛客584837756号
编辑于 2021-07-31 21:33
+ 关注

科大讯飞 2022届 秋招 测试类 笔试 填空题 编程题

分值分布:单选题(60分),填空题(20分),编程题(20分)
单选题里面,有测试样例、树的遍历、C++、Python、SQL、Java、操作系统
填空题和编程题都只有一道。
填空题:什么叫好的输入法,写出具体指标和测试方法。
编程题:

题目描述

飞飞有一个长度为 n 的数组 a,飞妹给了飞飞 m 个锦囊,第 i 个锦囊内有两个数字 ,如果飞飞使用了第 i 个锦囊,那么飞飞就可以在 a 中选择最多 个元素将它们全部变成 。飞飞想使用一些锦囊使得数组 a 所有元素的和最大,请你帮助飞飞求出这个最大值。

注:每个锦囊只能使用一次。

输入描述

第一行输入两个正整数 n,m 表示数组的长度和锦囊的个数。
第二行输入 n 个正整数表示数组 a 。
接下来 m 行,每行输入两个正整数,第 i 行的正整数为

输出描述

输出一个正整数表示答案。

示例1

输入:
5 3
1 2 3 4 5
1 5
4 4
3 1
输出:
22
说明:
使用第 1 个锦囊,将 变成 5 ,使用第 2 个锦囊,将 变成  4,最终 ,因此答案为 5+4+4+4+5=22 是最大值 。

示例2

输入:
3 1
3 3 3
1 5
输出:
11
说明:
使用第 1 个锦囊,随便选择一个元素将其变成 5 ,答案是 11 。

我的代码

按着题目的思路写,一出来就是 19% 通过率,超时。
在使用锦囊之前排序一下数组,把数字最小的放在前面,变成了 28% 超时
加了一下 flag 判断,这次没有变化就提前退出,变成了 38% 超时
最后在每次使用完一个锦囊后排序了一下数组 95% 超时
差不多了,我已经满足了。。
import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
import java.util.Scanner;

public class Main {
    public static void main (String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int m = sc.nextInt();
        int[] a = new int[n];
        List<int[]> jin = new ArrayList<int[]>(m);
        for(int i = 0; i < n; i++){
            a[i] = sc.nextInt();
        }
        for(int i = 0; i < m; i++){
            jin.add(i, new int[]{sc.nextInt(), sc.nextInt()});
        }
        Arrays.sort(a); // 28.57% 超时
        jin.sort((i, j) -> {
            if (i[1] != j[1]) return j[1] - i[1];
            if (i[0] != j[0]) return j[0] - i[0];
            return 0;
        });
        for (int i = 0; i < jin.size(); i++){  // 使用第 i 个锦囊
            int count = jin.get(i)[0];
            int value = jin.get(i)[1];
            if(value < a[0]) break;
            boolean flag = false;  // 本次循环有没有使用锦囊
            for(int j = 0; j < count; j++){  // 锦囊可以修改 j 个元素
                for(int k = 0; k < a.length; k++){  // 遍历数组
                    if(a[k] < value){
                        a[k] = value;
                        flag = true;
                        break;
                    }
                }
                if(!flag) break;  // 38.1% 超时
            }
            Arrays.sort(a);  // 95.24% 超时
        }
        long sum = 0;
        for(int i = 0; i < a.length; i++){
            sum += a[i];
        }
        System.out.println(sum);
    }
}

全部评论

(0) 回帖
加载中...
话题 回帖

推荐话题

相关热帖

近期热帖

历年真题 真题热练榜 24小时
技术(软件)/信息技术类
查看全部

近期精华帖

热门推荐