解题思路: 每次都排序,没意思。整点新玩意,有插入排序那个意思。
Deque双端队列,既有队列的特性,又有栈的特性。
res和tempDeque保存的数据始终有序,从高到底。
每次从res队尾插一个元素,就与res中的队尾比较,
1.如果插入元素比队尾元素小,直接插入
2.如果插入元素比队尾元素大,将res队尾元素尾插到tempDeque中,继续走1.
3.插入完该元素后,将tempDeque中的元素从对头到队尾依次尾插到res中,res依然有序
注意事项:
参考代码:
import java.util.*; /** * @author fzy * @create 2021/10/9 15:28 **/ public class t2328 { static class Node{ Integer no; Double score; } public static void main(String[] args) { Scanner sc=new Scanner(System.in); int n = sc.nextInt();//n个学生 int k = sc.nextInt();//第k名 Deque<Node> res=new LinkedList<Node>(); Deque<Node> tempDeque=new LinkedList<Node>(); for (int i=0;i<n;i++){ Node node = new Node(); node.no=sc.nextInt();//学号 node.score=sc.nextDouble();//成绩 if(res.isEmpty()){ res.offerLast(node);//队尾加入 }else{ while (true){ //查看队尾元素 如果队列无元素 返回null Node lastNode = res.peekLast(); if(lastNode !=null && node.score>lastNode.score){ tempDeque.offerLast(res.pollLast());//弹出队尾元素 将其加入临时队列尾 }else{ res.offerLast(node);//队空时或当前插入结点小于res中尾结点时 直接加入尾部 break; } } while (!tempDeque.isEmpty()){ res.offerLast(tempDeque.pollLast()); } } } int count=0; for (Node re : res) { if(count==k-1){ System.out.println(re.no+" "+re.score); break; } count++; } } }
0.0分
1 人评分
printf基础练习2 (C语言代码)浏览:566 |
【回文数(二)】 (C语言代码)浏览:728 |
最长单词 (C语言代码)浏览:1355 |
哥德巴赫曾猜测 (C语言代码)浏览:2295 |
母牛的故事 (C语言代码)浏览:1426 |
C语言训练-自由落体问题 (C语言代码)浏览:609 |
1013题解浏览:552 |
1124题解浏览:591 |
C语言程序设计教程(第三版)课后习题9.4 (C语言代码)浏览:628 |
C语言程序设计教程(第三版)课后习题6.10 (C语言代码)浏览:505 |