思路：大根堆+模拟

给定 $M$ 个数据，每个数据为 $A$ 个重复的 $B$ 。要求每读入一次数据，最多输出当前已读数据中最大的 $N$ 个值。

为了能够快速得到最大的值，我们可以使用大根堆来对数据进行存储。

什么是大根堆？

其学名是优先队列。具体表现形式(或者说我们自己手动模拟的形式)是一颗二叉树，每个结点最多有两个儿子，且对于任意一个结点，都符合：该结点任意儿子的值，都比该结点的值小。因此，堆顶(或者说二叉树的根节点)就是所有数中最大的值。

对于C++选手来说，刚好有STL能够使用，即priority_queue，其默认是大根堆。比较基础的几个函数分别是：

1. pop()，弹出堆顶，并返回该元素
2. push(x)，将 $x$ 加入到堆中
3. size()，返回堆中当前元素的个数
4. clear()，清空堆

其他语言也有相应的封装包，比如python里有heapq。因此如果自己不想动手实现一个优先队列的话，可以直接使用封装包。

由于该题的数据量很小，我们可以直接借助大根堆来模拟这个过程。

具体过程如下：

1. 读入一行数据，将其加入到大根堆q中
2. 从大根堆不断取出堆顶，进行输出，并将该数据放入到临时队列tmp中，直到输出一共 $N$ 个数字
3. 将tmp中的数据再重新放回堆中

由于 $N$ 很小，最大仅为24，也就是说每次最多输出24个字符，而堆的每次操作都可以近似看作 $O(logM)$ 的，最坏情况下每次取出堆中24个数据(每个数据只重复1次)输出再放回去也就是 $O(NlogM)$ 的时间复杂度。读入 $M$ 行数据，总共要输出 $M$ 次，因此总时间复杂度为 $O(NMlogM)$。

代码

C++

#include <iostream>
#include <cstdio>
#include <queue>
using namespace std;

int n,m;

struct node{
	int cnt;// 重复多少次 
	int val;// 值 
};

queue<node> tmp;
priority_queue<node> q;

bool operator <(const node a,const node b){// 重载运算符 
	return a.val<b.val;
}

int main(){
	scanf("%d %d",&n,&m);
	node a;
	for(int i=1,rest;i<=m;++i){
		scanf("%d %d",&a.cnt,&a.val);
		q.push(a);
		rest=n;// rest为输出某一字符后，剩余的长度，初始为n 
		while(rest>0){
			if(!q.size()) break;// 大根堆里已经没有字符了，直接break 
			// 取出堆顶 
			a=q.top();
			q.pop();
			// 输出 min(rest,a.cnt) 次 
			for(int i=1;i<=min(rest,a.cnt);++i){
				printf("%d",a.val);
			}
			// 从堆里取出来放到临时队列中 
			tmp.push(a);
			rest-=a.cnt;
		}
		while(tmp.size()){// 将队列中的数据重新放回堆中 
			q.push(tmp.front());
			tmp.pop();
		}
		printf("\n");
	}
	
	
	return 0;
}

python

import heapq

class Node:
    def __init__(self, cnt, val):
        self.cnt = cnt
        self.val = val
    
    def __lt__(self, other):
        return self.val > other.val

n, m = map(int, input().split())

q = []
tmp = []

for _ in range(m):
    cnt, val = map(int, input().split())
    heapq.heappush(q, Node(cnt, val))
    rest = n  # rest为输出某一字符后，剩余的长度，初始为n
    while rest > 0:
        if not q:
            break  # 大根堆里已经没有字符了，直接break
        # 取出堆顶
        a = heapq.heappop(q)
        # 输出 min(rest,a.cnt) 次
        for _ in range(min(rest, a.cnt)):
            print(a.val, end="")
        # 从堆里取出来放到临时队列中
        tmp.append(a)
        rest -= a.cnt
    while tmp:
        # 将队列中的数据重新放回堆中
        heapq.heappush(q, tmp.pop(0))
    print()

Java

import java.util.*;
import java.io.*;

public class Main {
    // 定义节点类，包含重复次数和值
    static class Node {
        long cnt; // 重复次数
        int val;  // 值

        Node(long cnt, int val) {
            this.cnt = cnt;
            this.val = val;
        }
    }

    public static void main(String[] args) throws IOException {
        // 使用BufferedReader提高输入效率
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String[] first = br.readLine().trim().split("\\s+");
        int N = Integer.parseInt(first[0]); // 最大保留个数
        int M = Integer.parseInt(first[1]); // 输入行数

        // 定义大根堆，按照val从大到小排序
        PriorityQueue<Node> pq = new PriorityQueue<>(new Comparator<Node>() {
            public int compare(Node a, Node b) {
                return b.val - a.val; // 大根堆
            }
        });

        // 临时队列，用于存储当前批次取出的节点
        Queue<Node> tmp = new LinkedList<>();

        // 处理每一批输入
        for(int i=0;i<M;i++) {
            String[] line = br.readLine().trim().split("\\s+");
            long A = Long.parseLong(line[0]); // 重复次数
            int B = Integer.parseInt(line[1]); // 值
            pq.offer(new Node(A, B)); // 将节点加入优先级队列

            long rest = N; // 剩余需要取的个数
            StringBuilder sb = new StringBuilder(); // 存储当前输出

            // 取出当前最大的N个元素
            while(rest > 0 && !pq.isEmpty()) {
                Node current = pq.poll(); // 取出当前最大值
                long k = Math.min(rest, current.cnt); // 取出次数不超过剩余需要的个数
                // 将当前值k次添加到输出中
                for(int j=0; j<k; j++) {
                    sb.append(current.val);
                }
                tmp.offer(current); // 将当前节点暂存
                rest -= k; // 更新剩余需要的个数
            }

            // 将暂存的节点重新加入优先级队列
            while(!tmp.isEmpty()) {
                pq.offer(tmp.poll());
            }

            // 输出当前队列的结果
            System.out.println(sb.toString());
        }
    }
}

Go

package main

import (
	"container/heap"
	"fmt"
)

type Node struct {
	cnt int // 重复多少次
	val int // 值
}

type PriorityQueue []Node

func (pq PriorityQueue) Len() int { return len(pq) }
func (pq PriorityQueue) Less(i, j int) bool {
	return pq[i].val < pq[j].val
}
func (pq PriorityQueue) Swap(i, j int) {
	pq[i], pq[j] = pq[j], pq[i]
}
func (pq *PriorityQueue) Push(x interface{}) {
	item := x.(Node)
	*pq = append(*pq, item)
}
func (pq *PriorityQueue) Pop() interface{} {
	old := *pq
	n := len(old)
	item := old[n-1]
	*pq = old[0 : n-1]
	return item
}

func main() {
	var n, m int
	fmt.Scan(&n, &m)
	q := make(PriorityQueue, 0)
	tmp := make(PriorityQueue, 0)

	for i := 0; i < m; i++ {
		var a Node
		fmt.Scan(&a.cnt, &a.val)
		heap.Push(&q, a)
		rest := n // rest为输出某一字符后，剩余的长度，初始为n
		for rest > 0 {
			if len(q) == 0 {
				break // 大根堆里已经没有字符了，直接break
			}
			// 取出堆顶
			a := heap.Pop(&q).(Node)
			// 输出 min(rest,a.cnt) 次
			for j := 0; j < min(rest, a.cnt); j++ {
				fmt.Print(a.val)
			}
			// 从堆里取出来放到临时队列中
			heap.Push(&tmp, a)
			rest -= a.cnt
		}
		for len(tmp) > 0 {
			// 将队列中的数据重新放回堆中
			heap.Push(&q, heap.Pop(&tmp).(Node))
		}
		fmt.Println()
	}
}

func min(a, b int) int {
	if a < b {
		return a
	}
	return b
}

Js

const readline = require('readline');

function min(a, b) {
  return a < b ? a : b;
}

const rl = readline.createInterface({
  input: process.stdin,
  output: process.stdout
});

let n, m;
const q = [];
const tmp = [];

rl.on('line', (line) => {
  const input = line.split(' ').map(Number);
  if (!n) {
    [n, m] = input;
    return;
  }
  const [cnt, val] = input;
  q.push({ cnt, val });
  let rest = n; // rest为输出某一字符后，剩余的长度，初始为n
  while (rest > 0) {
    if (q.length === 0) break; // 大根堆里已经没有字符了，直接break
    // 取出堆顶
    const a = q.shift();
    // 输出 min(rest,a.cnt) 次
    for (let i = 0; i < min(rest, a.cnt); i++) {
      process.stdout.write(String(a.val));
    }
    // 从堆里取出来放到临时队列中
    tmp.push(a);
    rest -= a.cnt;
  }
  while (tmp.length > 0) {
    // 将队列中的数据重新放回堆中
    q.push(tmp.shift());
  }
  process.stdout.write('\n');
});

题目内容

小明面临一个挑战，需要从海量的网络数据中筛选出繁忙时段的数据。考虑到数据规模庞大，小明无法对所有数据进行排序，然后选择前$N$个最大值作为繁忙时段的数据。聪明的小明想到了使用一个固定大小的优先级队列来筛选数据。为了简化场景，我们将海量网络数据表示为一个正整数集合，并且仅需选择$N$个最大的正整数作为结果。对于每批输入数据，小明将输出一行结果，将这$N$个正整数按照顺序拼接成一行字符串进行输出。

输入描述

输入第一行为正整数$N$和$M$，$N$为忙时个数，$M$为输入的数据行数，($1$ $\leq$ $N$ $\leq$ $24$ ，$1$ $\leq$ $M$ $\leq$ $1000$)

接下来输入$M$行，每行两个正整数$A，B$，以空格分隔，表示有$A$个重复的正整数$B$，$1$ $\leq$ $A$,$B$ $\leq$ $2147483647$ 。

输出描述

输出每增加一批数据对应的队列结果，直接将队列里的所有数据集从大到小拼接成字符串输出.

样例1

输入

24 3
11 5
2 1
18 7

输出

55555555555
5555555555511
777777777777777777555555

解释

保留$24$个忙时数据

第一次输入$11$个$5$，则队列输出为$55555555555$

第二次输入$2$个$1$，则队列输出为$5555555555511$

第三次输入$18$个$7$，则队列输出为$777777777777777777555555$