首页 > 试题广场 >

一种消息接收并打印的结构设计

[编程题]一种消息接收并打印的结构设计
  • 热度指数:612 时间限制:C/C++ 2秒,其他语言4秒 空间限制:C/C++ 256M,其他语言512M
  • 算法知识视频讲解
已知一个消息流会不断地吐出整数,但不一定按照顺序吐出。如果上次打印的数为i,那么当i+1出现时,请打印i+1及其之后接收过的并且连续的所有数,直到全部接收并打印完,请设计这种接收并打印的结构
[要求]
消息流最终会吐出全部的,当然最终也会打印完所有的,要求接收和打印的整个过程,时间复杂度为

输入描述:
第一行一个整数N。

接下来一行有N个整数。保证输入是一个1到N的排列


输出描述:
输出N行,每行两个数。

为了检验输出的正确性,请在输出当前打印的数字之后输出此时最后一个加入的元素。

具体看输入输出样例
示例1

输入

9
2 1 4 5 7 3 9 8 6

输出

1 1
2 1
3 3
4 3
5 3
6 6
7 6
8 6
9 6

说明

消息流吐出2,一种结构接收而不打印2,因为1还没出现。
消息流吐出1,一种结构接收1,并且打印:1, 2。
消息流吐出4,一种结构接收而不打印4,因为3还没出现。
消息流吐出5,一种结构接收而不打印5,因为3还没出现。
消息流吐出7,一种结构接收而不打印7,因为3还没出现。
消息流吐出3,一种结构接收3,并且打印:3, 4, 5。
消息流吐出9,一种结构接收而不打印9,因为6还没出现。
消息流吐出8,一种结构接收而不打印8,因为6还没出现。
消息流吐出6,一种结构接收6,并且打印:6, 7, 8, 9。

备注:
保证输入的是一个的排列
#include <bits/stdc++.h>
using namespace std;

int main(){
    int n;
    cin>>n;
    int a[n], Min=1, k=1;
    priority_queue<int, vector<int>, greater<int>> q;
    for(int i=0;i<n;i++){
        cin>>a[i];
        q.push(a[i]);
        if(a[i]==Min)
            while(q.top()==Min){
                cout<<k++<<" "<<a[i]<<endl;
                Min++;
                q.pop();
            }
    }
    return 0;
}

编辑于 2020-04-01 00:31:25 回复(0)
一个布尔数组record记录吐出的数,next记录需要的下一个数。
import java.util.*;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        while (sc.hasNext()) {
            int n=Integer.parseInt(sc.nextLine().trim());
            int[] arr=new int[n];
            String[] s = sc.nextLine().trim().split(" ");
            for (int i = 0; i < n; i++) {
                arr[i]=Integer.parseInt(s[i]);
            }
            List<int[]> res=new Solution().getPrintProcess(arr);
            for (int i = 0; i < res.size(); i++) {
                System.out.println(res.get(i)[0]+" "+res.get(i)[1]);
            }
        }
    }
}

class Solution {
    public List<int[]> getPrintProcess(int[] arr){
        List<int[]> res=new ArrayList<>();
        boolean[] record=new boolean[arr.length+1];
        int next=1;
        for (int i = 0; i < arr.length; i++) {
            record[arr[i]]=true;
            while (next<record.length&&record[next]){
                res.add(new int[]{next,arr[i]});
                next++;
            }
        }
        return res;
    }
}


发表于 2022-05-26 16:31:26 回复(0)
import java.util.*;
public class Main{
    public static void main(String[] args){
        Scanner sc=new Scanner(System.in);
        while(sc.hasNext()){
            int n=sc.nextInt();
            int m=1;
            StringBuilder sb=new StringBuilder();
            Set<Integer> set=new HashSet<>();
            for(int i=0;i<n;i++){
                int tmp=sc.nextInt();
                if(tmp!=m){
                    set.add(tmp);
                    continue;
                }
                while(tmp==m||set.contains(m)){
                    sb.append(m).append(" ").append(tmp).append("\n");
                    m++;
                }
            }
            System.out.println(sb.toString());
        }
        sc.close();
    }
}

发表于 2021-04-08 20:25:21 回复(0)
import java.io.*;
import java.util.*;
  
public class Main{
    public static void main(String[] args) {
        Scanner sc=new Scanner(System.in);
        int N=sc.nextInt();
        int[] ss=new int[N];
        for(int i=0;i<N;i++){
            ss[i]=sc.nextInt();
        }
        MessageBox mb = new MessageBox();
        for(int i = 0; i < ss.length; i++){
            mb.receive(ss[i]);
        }
    }
}
 class MessageBox{
    private HashMap<Integer,Node> headMap;
    private HashMap<Integer,Node> tailMap;
    private int lastPrint;
    public MessageBox(){
        headMap = new HashMap<Integer,Node>();
        tailMap = new HashMap<Integer,Node>();
        lastPrint = 0;
    }
    
    public void receive(int num){
        if(num < 0) return;
        Node cur = new Node(num);
        headMap.put(num,cur);
        tailMap.put(num,cur);
        if(tailMap.containsKey(num - 1)){
            Node pre = tailMap.get(num - 1);
            pre.next = cur;
            tailMap.remove(num - 1);
            headMap.remove(num);
        }
        if(headMap.containsKey(num + 1)){
            cur.next = headMap.get(num + 1);
            headMap.remove(num + 1);
            tailMap.remove(num);
        }
        if(headMap.containsKey(lastPrint + 1)){
            print();
        }
    }
    public void print(){
        int curInput = lastPrint + 1;
        Node node = headMap.get(curInput);
        headMap.remove(curInput);
        while(node != null){
            System.out.println(node.value + " " + curInput);
            node = node.next;
            lastPrint++;
        }
        tailMap.remove(lastPrint);
    }
}

class Node{
    public int value;
    public Node next;
    public Node(int value){
        this.value = value;
    }
}

发表于 2021-03-25 13:43:14 回复(0)