月饼是久负盛名的中国传统糕点之一，自唐朝以来，已经发展出几百品种。
若想评比出一种“最好吃”的月饼，那势必在吃货界引发一场腥风血雨…… 在这里我们用数字说话，给出全国各地各种月饼的销量，要求你从中找出销量冠军，认定为最好吃的月饼。
输入格式：
输入首先给出两个正整数?N（≤1000）和?M（≤100），分别为月饼的种类数（于是默认月饼种类从 1 到?N?编号）和参与统计的城市数量。
接下来?M?行，每行给出?N?个非负整数（均不超过 1 百万），其中第?i?个整数为第?i?种月饼的销量（块）。数字间以空格分隔。
输出格式：
在第一行中输出最大销量，第二行输出销量最大的月饼的种类编号。如果冠军不唯一，则按编号递增顺序输出并列冠军。数字间以 1 个空格分隔，行首尾不得有多余空格。
输入样例：
5 3
1001 992 0 233 6
8 0 2018 0 2008
36 18 0 1024 4输出样例：
2018
3 5解法一：
解题思路：
用map集合存储某个月饼的种类和其销量的对应关系，将对应关系写入类中，通过实现Comparable接口对其排序。（较繁琐）（超时）
解题代码：
import java.io.*;
import java.util.*;
public class Main {
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
String[] split = br.readLine().split(" ");
int sort = Integer.parseInt(split[0]);
int n = Integer.parseInt(split[1]);
Map<Integer,Integer> map = new HashMap<Integer,Integer>();
for(int i = 0; i < n;i++) {
split = br.readLine().split(" ");
for(int j = 0; j < split.length;j++) {
Integer value = map.get(j + 1);
if(value != null) {
map.put(j + 1, value + Integer.parseInt(split[j]));
}else {
map.put(j + 1, Integer.parseInt(split[j]));
}
}
}
Set<Integer> keySet = map.keySet();
List<MoonCake> list = new ArrayList<MoonCake>();
Iterator<Integer> iterator = keySet.iterator();
while(iterator.hasNext()) {
Integer key = iterator.next();
Integer value = map.get(key);
list.add(new MoonCake(key, value));
}
Collections.sort(list);
int max = list.get(0).count;
System.out.println(max);
Iterator<MoonCake> iterator2 = list.iterator();
List<Integer> list2 = new ArrayList<Integer>();
for(int i = 0; i < list.size();i++) {
if(list.get(i).count == max) {
list2.add(list.get(i).sort);
}else {
break;
}
}
for(int i = 0;i < list2.size() - 1;i++) {
System.out.print(list2.get(i) + " ");
}
System.out.print(list2.get(list2.size() - 1));
}
}
class MoonCake implements Comparable<MoonCake>{
int sort;
int count;
public MoonCake(int sort, int count) {
this.sort = sort;
this.count = count;
}
@Override
public int compareTo(MoonCake o) {
if(this.count != o.count)
return o.count - this.count;
else
return this.sort - o.sort;
}
}PTA提交截图：
解法二：
解题思路：
由于每个城市间的月饼种类都是相互独立的，所以直接将从第二个城市以后的月饼种类数，都叠加到第一个城市的月饼上，直接用一个数组解决。（仍超时）
解题代码：
import java.io.*;
import java.util.*;
public class Main {
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
String[] split = br.readLine().split(" ");
int n = Integer.parseInt(split[0]);
int m = Integer.parseInt(split[1]);
int []arr = new int [n];
int max = 0;
for(int i = 0; i < m; i++) {
split = br.readLine().split(" ");
for(int j = 0; j < n;j++) {
arr[j] += Integer.parseInt(split[j]);
if(arr[j] > max) max = arr[j];
}
}
System.out.println(max);
List<Object> list = new ArrayList<>();
for(int i = 0; i < n;i++) {
if(arr[i] == max)
list.add(i + 1);
}
for(int i = 0; i < list.size() - 1;i++) {
System.out.print(list.get(i) + " ");
}
System.out.print(list.get(list.size() - 1));
}
}
PTA提交截图：
