分值分布：单选题（60分），填空题（20分），编程题（20分）
单选题里面，有测试样例、树的遍历、C++、Python、SQL、Java、操作系统
填空题和编程题都只有一道。
填空题：什么叫好的输入法，写出具体指标和测试方法。
编程题：
题目描述
飞飞有一个长度为 n 的数组 a，飞妹给了飞飞 m 个锦囊，第 i 个锦囊内有两个数字 ，如果飞飞使用了第 i 个锦囊，那么飞飞就可以在 a 中选择最多 个元素将它们全部变成
。飞飞想使用一些锦囊使得数组 a 所有元素的和最大，请你帮助飞飞求出这个最大值。
注：每个锦囊只能使用一次。
输入描述
第一行输入两个正整数 n,m 表示数组的长度和锦囊的个数。
第二行输入 n 个正整数表示数组 a 。
接下来 m 行，每行输入两个正整数，第 i 行的正整数为
。
第二行输入 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) 回帖