已知一个消息流会不断地吐出整数,但不一定按照顺序吐出。如果上次打印的数为i,那么当i+1出现时,请打印i+1及其之后接收过的并且连续的所有数,直到全部接收并打印完,请设计这种接收并打印的结构
[要求]
消息流最终会吐出全部的,当然最终也会打印完所有的,要求接收和打印的整个过程,时间复杂度为。
第一行一个整数N。
接下来一行有N个整数。保证输入是一个1到N的排列
输出N行,每行两个数。
为了检验输出的正确性,请在输出当前打印的数字之后输出此时最后一个加入的元素。
具体看输入输出样例
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; }
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; } }
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(); } }
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; } }