计科院19软工范征远


私信TA

用户名:1954418428

访问量:1144

签 名:

等  级
排  名 20943
经  验 633
参赛次数 1
文章发表 8
年  龄 0
在职情况 学生
学  校 怀化学院
专  业

  自我简介:

解题思路: 每次都排序,没意思。整点新玩意,有插入排序那个意思。
                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 人评分

  评论区