老师想知道从某某同学当中,分数最高的是多少,现在请你编程模拟老师的询问。当然,老师有时候需要更新某位同学的成绩.
输入描述:
输入包括多组测试数据。 每组输入第一行是两个正整数N和M(0 < N <= 30000,0 < M < 5000),分别代表学生的数目和操作的数目。 学生ID编号从1编到N。 第二行包含N个整数,代表这N个学生的初始成绩,其中第i个数代表ID为i的学生的成绩 接下来又M行,每一行有一个字符C(只取‘Q’或‘U’),和两个正整数A,B,当C为'Q'的时候, 表示这是一条询问操作,他询问ID从A到B(包括A,B)的学生当中,成绩最高的是多少 当C为‘U’的时候,表示这是一条更新操作,要求把ID为A的学生的成绩更改为B。
输出描述:
对于每一次询问操作,在一行里面输出最高成绩.
输入例子:
5 7 1 2 3 4 5 Q 1 5 U 3 6 Q 3 4 Q 4 5 U 4 5 U 2 9 Q 1 5
输出例子:
5 6 5 9
这道题并不难,思路也挺简单,主要的是在于存储学生成绩以及选择最大的成绩,刚开始我考虑使用Map键值对的形式存储学生的ID以及对应的成绩,有HashMap,TreeMap可以选择,其实选择List也可以存储,但是Map相比List有一个很大好处就是,在更新学生成绩时,Map的put(key,value)方法可以直接覆盖原来对应key的value值,若是使用List,使用add(index,E element)方法后,还需要删除index+1处的元素,因为原来index处的元素会被向下移一位,即需要remove(index+1);List的set(int index,E element)可以实现)
1 import java.util.ArrayList; 2 import java.util.Collections; 3 import java.util.List; 4 import java.util.Map; 5 import java.util.Scanner; 6 import java.util.TreeMap; 7 8 public class MaxScore { 9 10 public static void main(String[] args) { 11 Map<Integer, Integer> mp = new TreeMap<Integer, Integer>(); 12 Scanner sc = new Scanner(System.in); 13 while (sc.hasNextLine()) { 14 String s = sc.nextLine(); 15 String[] st = s.split(" "); 16 String n = st[0]; 17 String m = st[1]; 18 String score = sc.nextLine(); 19 for (int i = 1; i <= Integer.valueOf(n); i++) { 20 String[] st1 = score.split(" "); 21 mp.put(i, Integer.valueOf(st1[i - 1])); 22 } 23 List<Integer> li = new ArrayList<Integer>(); 24 for (int i = 0; i < Integer.valueOf(m); i++) { 25 String s1 = sc.nextLine(); 26 String[] str = s1.split(" "); 27 if (str[0].equals("Q")) { 28 int start=0,end=0; 29 start = Math.min(Integer.valueOf(str[1]), Integer.valueOf(str[2])); 30 end = Math.max(Integer.valueOf(str[1]), Integer.valueOf(str[2])); 31 for (int j = start; j <= end; j++) { 32 li.add(mp.get(j)); 33 } 34 Collections.sort(li); 35 System.out.println(li.get(li.size() - 1)); 36 li.clear(); 37 } 38 39 if (str[0].equals("U")) { 40 mp.put(Integer.valueOf(str[1]), Integer.valueOf(str[2])); 41 } 42 } 43 44 } 45 } 46 }
但是上面的写好过于繁琐,复杂度过高,无法AC,尤其是我接收是以一行字符串接受,然后再分割,然后转为Integer,代码比较冗余,于是我改为整数型接收输入:
1 import java.util.ArrayList; 2 import java.util.Collections; 3 import java.util.List; 4 import java.util.Map; 5 import java.util.Scanner; 6 import java.util.TreeMap; 7 8 public class Temp7 { 9 10 public static void main(String[] args) { 11 Map<Integer, Integer> mp = new TreeMap<Integer, Integer>(); 12 Scanner sc = new Scanner(System.in); 13 while (sc.hasNext()) { 14 int n = sc.nextInt(); 15 int m = sc.nextInt(); 16 for (int i = 1; i <= n; i++) { 17 mp.put(i, sc.nextInt()); 18 } 19 List<Integer> li = new ArrayList<Integer>(); 20 for (int i = 0; i < m; i++) { 21 String c = sc.next(); 22 int a = sc.nextInt(); 23 int b = sc.nextInt(); 24 if (c.equals("Q")) { 25 int start = 0, end = 0; 26 start = Math.min(a, b); 27 end = Math.max(a, b); 28 for (int j = start; j <= end; j++) { 29 li.add(mp.get(j)); 30 } 31 Collections.sort(li); 32 System.out.println(li.get(li.size() - 1)); 33 li.clear(); 34 } 35 if (c.equals("U")) { 36 mp.put(a, b); 37 } 38 } 39 40 } 41 } 42 }
代码似乎简洁了一些,但是系统还是提示时间超过限制"运行超时:您的程序未能在规定时间内运行结束,请检查是否循环有错或算法复杂度过大。",复杂度过高,比较郁闷,参考别人代码,发现有人使用数组存储并且在判断大小时循环判断,经过反复试验,确定不是存储问题,而是在判断大小时出现了问题,可能系统认为我这样判断耗时,故该为循环判断解决超时问题;
1 import java.util.Map; 2 import java.util.Scanner; 3 import java.util.TreeMap; 4 5 public class Main { 6 7 public static void main(String[] args) { 8 Map<Integer, Integer> mp = new TreeMap<Integer, Integer>(); 9 Scanner sc = new Scanner(System.in); 10 while (sc.hasNext()) { 11 int n = sc.nextInt(); 12 int m = sc.nextInt(); 13 for (int i = 1; i <= n; i++) { 14 mp.put(i, sc.nextInt()); 15 } 16 //List<Integer> li = new ArrayList<Integer>(); 17 for (int i = 0; i < m; i++) { 18 String c = sc.next(); 19 int a = sc.nextInt(); 20 int b = sc.nextInt(); 21 if (c.equals("Q")) { 22 int start = 0, end = 0; 23 start = Math.min(a, b); 24 end = Math.max(a, b); 25 int max=mp.get(start); 26 for (int j = start; j <= end; j++) { 27 //li.add(mp.get(j)); 28 if(max<mp.get(j)){ 29 max = mp.get(j); 30 } 31 32 } 33 System.out.println(max); 34 // Collections.sort(li); 35 // System.out.println(li.get(li.size() - 1)); 36 // li.clear(); 37 } 38 if (c.equals("U")) { 39 mp.put(a, b); 40 } 41 } 42 43 } 44 } 45 }