PAT 1109 Group Photo [Java]
JAVA group PAT photo
2023-09-14 09:13:22 时间
PAT 1109 Group Photo
【java 超时】
1. 题意
在为集体拍照时,构成规则是非常重要的。给出为N 个人站成K 行的规则如下:
- 每行的人数必须是N/K (向下取整),所有的剩下的人(如果有的话)站在最后一排
- 后一行的人必须不矮于前一行的人
- 每行中,最高的人站在中间的位置(定义成:m/2 + 1),m是该行人的总数, 除法的结果必须向下取整。
- 每行中,其它的人必须按照 从高到矮(non-increasing order) 的顺序依次入队。入队的规则是:先到该行中最高的人的右 -> 左的顺序。
- 如果身高有相同的,那么按照姓名进行排序
2.简单示例
如下给出一行中排队的示例,假设现在有5个人,身高分别是:190, 188, 186, 175, 170
。 那么这五个人入队的顺序如下:
190
=>
188 190
=>
188 190 186
=>
175 188 190 186 170
最后的队形就是: 175, 188, 190, 186, 170
如果遇到有相同身高的人,则按照姓名进行站队。
例如,有如下三个人,其中Eva 和 Ann的身高相同:于是得到的排序应该是
Mike=170 ,Ann=168,Eva=168
而不是Mike=170 ,Eva=168,Ann=168
。根据排序得到的站队就是:
Ann=168
Mike=170
Eva=168
而不是:
Eva=168
Mike=170
Ann=168
3.解题思路
- step 1: 对于所有的人,由身高从高到底进行排序(如果是有身高相同的,按照姓名排序)
- step 2: 接着计算需要站成多少行,每行多少人(一般只有最后一行的人会超出普通行)?
- step 3: 接着对每一行的人进行站队,如:
190, 188, 186, 175, 170
,先安排最高个的人,接着在最高个的左边安排188,175。(i=1;i<number;i+=2) - step 4:左边安排完之后,在右边接着安排,使用(i=2;i<number;i+=2),即可
4.代码
下面给出java 代码
import java.util.*;
public class Main {
private static Map<String, Integer> student = new HashMap<String, Integer>();
private static List<Map.Entry<String, Integer>> lists ;
public static void main(String[] args) {
Scanner in = new Scanner(System.in);
int totalNumber = in.nextInt();//总人数
int lineNumber = in.nextInt();//每行的人数
in.nextLine();
String line[];
String name;
int height;
for (int i = 0; i < totalNumber; i++) {
line = in.nextLine().trim().split(" ");
name = line[0];
height = Integer.parseInt(line[1]);
student.put(name, height);
}
lists = new ArrayList<Map.Entry<String, Integer>>(student.entrySet());
sort();
//lineNumber 表示的是每行站队的人数
//List<Map.Entry<String, Integer>> rows = new ArrayList<>();
int rowNumber = totalNumber / lineNumber;
//这个result 是用于保存每行的站队人数的姓名
//但是不能用lineNumber 作为数组大小,因为可能会导致数组溢出
String[] result = new String[lineNumber*2];
//==============================================================第一行==============================================
int rest = totalNumber % lineNumber + lineNumber; // 最后一行站队的人数
int position = rest / 2 ; //表示每个人的下标 + 初始化值
result[rest/2] = lists.get(0).getKey(); //最高者的位置
for(int j = 1 ; j < rest ;j += 2) { //从左往右添加
position -= 1; //往前移一个下标
result[position] = lists.get(j).getKey(); //将姓名添加到其中
}
position = rest / 2 ;//reset
for(int j = 2 ; j < rest ;j += 2) { //从左往右添加
position ++;
result[position] = lists.get(j).getKey(); //将姓名添加到其中
}
//每行的站队排好之后 就输出
for(int k = 0;k < result.length;k++) { // invalid null
if (result[k] == null) {
System.out.println();//输出换行
break;
}
if (result[k+1] != null) {
System.out.print(result[k] + " ");
} else {
System.out.print(result[k]);
}
}
int j = 0;
while(j< rest) {
lists.remove(0);//删除前 lineNumber 个元素
j++;
}
//============================== 这个循环是用于找出每行的站队人数 => 但是不包括最后一行==============================================
//因为上面的结果对后面的计算可能有污染,所以需要重置结果
for(int z = 0;z< result.length;z++) {
result[z] = null;
}
for(int i = 0;i < rowNumber - 1 ;i++) {
result[lineNumber/2] = lists.get(0).getKey();
position = lineNumber/2;
for(j = 1;j < lineNumber ;j += 2) { //从左往右添加
position --;
result[position] = lists.get(j).getKey(); //将姓名添加到其中
}
position = lineNumber / 2 ;//reset -> 因为这个是从位置1开始存放
for( j = 2;j < lineNumber ;j += 2) { //从右往左添加
position ++;
result[position] = lists.get(j).getKey(); //将姓名添加到其中
}
//每行的站队排好之后 就输出
for(int k = 0;k < result.length;k++) { // invalid null
if (result[k] == null) {
System.out.println();//输出换行
break;
}
if (result[k+1] != null) {
System.out.print(result[k] + " ");
} else {
System.out.print(result[k]);
}
}
j = 0;
while(j< lineNumber) {
lists.remove(0);//删除前 lineNumber 个元素
j++;
}
}
//根据height and name 排序
public static void sort() {
Collections.sort(lists, new Comparator<Map.Entry<String, Integer>>() {
@Override
public int compare(Map.Entry<String, Integer> o1, Map.Entry<String, Integer> o2) {
int status = o1.getValue().compareTo(o2.getValue()) ;
if (status == 0) {
status = -1 * (o1.getKey().compareTo(o2.getKey())) ;
}
return -1 * status; //降序排序
}
});
}
}
/* 注意这里在John 159之后有一个换行。
10 3
Tom 188
Mike 170
Eva 168
Tim 160
Joe 190
Ann 168
Bob 175
Nick 186
Amy 160
John 159
10 3
Tom 188
Mike 170
Eva 168
Tim 158
Joe 190
Ann 168
Bob 175
Nick 186
Amy 160
John 159
10 4
Tom 188
Mike 170
Eva 168
Tim 160
Joe 190
Ann 168
Bob 175
Nick 186
Amy 160
John 159
3 3
Tim 160
Amy 160
John 159
3 3
Mike 170
Eva 168
Ann 168
3 3
Mike 170
Eva 170
Ann 168
4 3
Tom 188
Bob 175
Nick 186
Joe 190
*/
但是上述的这个代码不能全部AC,因为会有一部分数据是运行超时的,毕竟这不是C/C++。提交结果如下:
接着修改呗。
修改后的代码如下:
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStream;
import java.io.InputStreamReader;
import java.util.*;
public class Main {
private static Map<String, Integer> student = new HashMap<String, Integer>();
private static List<Map.Entry<String, Integer>> lists ;
public static void main(String[] args) throws IOException {
Reader.init(System.in);
int totalNumber = Reader.nextInt();//总人数
int lineNumber = Reader.nextInt();//每行的人数
String name;
int height;
for (int i = 0; i < totalNumber; i++) {
name = Reader.next();;
height = Integer.parseInt(Reader.next());
student.put(name, height);
}
lists = new ArrayList<Map.Entry<String, Integer>>(student.entrySet());
sort();
//lineNumber 表示的是每行站队的人数
//List<Map.Entry<String, Integer>> rows = new ArrayList<>();
int rowNumber = totalNumber / lineNumber;
//这个result 是用于保存每行的站队人数的姓名
//但是不能用lineNumber 作为数组大小,因为可能会导致数组溢出
String[] result = new String[lineNumber*2];
//==============================================================第一行==============================================
int rest = totalNumber % lineNumber + lineNumber; // 最后一行站队的人数
int position = rest / 2 ; //表示每个人的下标 + 初始化值
//System.out.println("最高个:"+ lists.get(rest-1).getKey());
result[rest/2] = lists.get(0).getKey(); //最高者的位置
for(int j = 1 ; j < rest ;j += 2) { //从左往右添加
position -= 1; //往前移一个下标
result[position] = lists.get(j).getKey(); //将姓名添加到其中
}
position = rest / 2 ;//reset
for(int j = 2 ; j < rest ;j += 2) { //从左往右添加
position ++;
result[position] = lists.get(j).getKey(); //将姓名添加到其中
}
//每行的站队排好之后 就输出
for(int k = 0;k < result.length;k++) { // invalid null
if (result[k] == null) {
System.out.println();//输出换行
break;
}
if (result[k+1] != null) {
System.out.print(result[k] + " ");
} else {
System.out.print(result[k]);
}
}
int j = 0;
while(j< rest) {
lists.remove(0);//删除前 lineNumber 个元素
j++;
}
//============================== 这个循环是用于找出每行的站队人数 => 但是不包括最后一行==============================================
//因为上面的结果对后面的计算可能有污染,所以需要重置结果
for(int z = 0;z< result.length;z++) {
result[z] = null;
}
for(int i = 0;i < rowNumber - 1 ;i++) {
result[lineNumber/2] = lists.get(0).getKey();
position = lineNumber/2;
for(j = 1;j < lineNumber ;j += 2) { //从左往右添加
position --;
result[position] = lists.get(j).getKey(); //将姓名添加到其中
}
position = lineNumber / 2 ;//reset -> 因为这个是从位置1开始存放
for( j = 2;j < lineNumber ;j += 2) { //从右往左添加
position ++;
result[position] = lists.get(j).getKey(); //将姓名添加到其中
}
//每行的站队排好之后 就输出
for(int k = 0;k < result.length;k++) { // invalid null
if (result[k] == null) {
System.out.println();//输出换行
break;
}
if (result[k+1] != null) {
System.out.print(result[k] + " ");
} else {
System.out.print(result[k]);
}
}
j = 0;
while(j< lineNumber) {
// System.out.println("待删除的list是:"+lists.get(0));
lists.remove(0);//删除前 lineNumber 个元素
j++;
}
}
}
//根据height and name 排序
public static void sort() {
Collections.sort(lists, new Comparator<Map.Entry<String, Integer>>() {
@Override
public int compare(Map.Entry<String, Integer> o1, Map.Entry<String, Integer> o2) {
int status = o1.getValue().compareTo(o2.getValue()) ;
if (status == 0) {
status = -1 * (o1.getKey().compareTo(o2.getKey())) ;
}
return -1 * status; //降序排序
}
});
}
}
class Reader {
static BufferedReader reader;
static StringTokenizer tokenizer;
/** call this method to initialize reader for InputStream */
static void init(InputStream input) throws IOException {
reader = new BufferedReader(new InputStreamReader(input) );
tokenizer = new StringTokenizer("");
//这里初始化tokenizer只是为了进入下面的while()循环,而不是别的原因。
//那么还有优化的空间么?
}
/** get next word */
static String next() throws IOException {
while ( ! tokenizer.hasMoreTokens() ) {//如果后面还有数据,则直接返回
//TODO add check for eof if necessary
tokenizer = new StringTokenizer(reader.readLine() );//否则,读取下一行
}
return tokenizer.nextToken();
}
static int nextInt() throws IOException {
return Integer.parseInt( next() );
}
static double nextDouble() throws IOException {
return Double.parseDouble( next() );
}
}
/* 注意这里在John 159之后有一个换行。
10 3
Tom 188
Mike 170
Eva 168
Tim 160
Joe 190
Ann 168
Bob 175
Nick 186
Amy 160
John 159
10 3
Tom 188
Mike 170
Eva 168
Tim 158
Joe 190
Ann 168
Bob 175
Nick 186
Amy 160
John 159
10 4
Tom 188
Mike 170
Eva 168
Tim 160
Joe 190
Ann 168
Bob 175
Nick 186
Amy 160
John 159
3 3
Tim 160
Amy 160
John 159
3 3
Mike 170
Eva 168
Ann 168
3 3
Mike 170
Eva 170
Ann 168
4 3
Tom 188
Bob 175
Nick 186
Joe 190
*/
提交之后,发现还是超时。
无可奈何【若有大佬,还望明示啊。】
相关文章
- Java多线程详解_java支持多线程
- java反转数组_Java实现数组反转翻转的方法实例
- 我的世界java版需要多少钱_我的世界Java版20w49a快照版[通俗易懂]
- java启动器_JAVA基础:Java 启动器如何查找类
- java motherfree video_Java Config 下的Spring Test方式
- java中文乱码_Java中文乱码问题的解决方案[通俗易懂]
- java有什么作用_Java有什么用「建议收藏」
- java运行机制是什么_JAVA运行机制
- 【说站】Java著作权结果出炉,谷歌战胜甲骨文
- 大牛即将带你深入解析java虚拟机:并发设施,内存模型
- java事务_Java 事务详解[通俗易懂]
- java中如何获取当前系统时间[通俗易懂]
- Java 变量命名规则[通俗易懂]
- Java将网络链接图片或者本地图片文件转换成Base64编码字符串
- 【Java面试八股文宝典之基础篇】备战2023 查缺补漏 你越早准备 越早成功!!!——Day11
- 【Java】邮件Demo(SSL加密传输)
- 【Java 网络编程】TCP 服务器端 客户端 简单示例
- MD5加密算法Java代码详解手机开发
- java生成二维码详解编程语言
- java发送邮件详解编程语言
- Java使用commons-net实现FTP文件上传详解编程语言
- Java虚拟机-类文件详解编程语言
- 解决Java程序连接MySQL数据库的方法(java链接mysql数据库)
- Java异步MySQL:开启数据处理新时代(java异步mysql)
- java内存模型详解编程语言
- 深入浅出Java配置MySQL数据库(java配置mysql)
- 缓存设置Java中Redis的过期缓存(redisjava过期)
- Java 关闭 Redis 连接的指南(java关闭redis)
- 时间的设置解决Java中Redis过期时间的设置(redisjava过期)
- Java连接Oracle实现简单快捷的数据传输(java联结oracle)