解题思路

• 将“缓存控制器”抽象为一个按“进入顺序”维护的容器，每个字符串只保留一份，并记录其累计出现次数。

• 每行读入后：

  1. 逐个字符串写入缓存：若不存在则按队尾插入并记数为 1；若已存在则在原位计数 +1（保持最早出现的顺序不变）。
  2. 立刻从缓存“最早”开始取出至多 n 个“不同字符串”，输出为「字符串 次数」对，并将这些键从缓存中删除；后续若同字符串再次进入，视为新键、重新计数。
  3. 若 n=0 或缓存为空，则输出 null。

• 核心算法

  • 维护一个“有序字典/映射”以保证“先进入先输出”的顺序，同时支持 O(1) 计数更新与删除最早元素。

  • 语言实现选型：

    • Python：collections.OrderedDict
    • Java：LinkedHashMap
    • C++：list + unordered_map（map 中存次数与 list 迭代器，既保序又可 O(1) 删除）

复杂度分析

• 设总输入字符串数为 M，每行输出上限为 n。
• 插入/计数更新：均摊 O(1)；按顺序输出并删除前 n 个键：O(n)。
• 总时间复杂度：O(M)（每个字符串至多被插入一次、计数若干次，且每个键至多被删除一次）。
• 空间复杂度：O(K)，K 为缓存中同时存在的不同字符串个数（不超过当下已读但未被取出的不同字符串数）。

代码实现

Python

# -*- coding: utf-8 -*-
# 题意：按行读入，维护有序缓存（字符串 -> 次数），每次读入后输出并删除至多 n 个最早键

import sys
from collections import OrderedDict

def process_line(cache: OrderedDict, tokens):
    """将本行 tokens 写入缓存：新词入队，旧词计数+1"""
    for t in tokens:
        if t == "":
            continue
        if t in cache:
            cache[t] += 1
        else:
            cache[t] = 1

def emit(cache: OrderedDict, n: int):
    """从缓存按先入先出取出至多 n 个不同字符串，拼接输出并删除"""
    if n == 0 or len(cache) == 0:
        print("null")
        return
    out = []
    k = 0
    # 由于要边遍历边删除，先收集要删的键
    to_remove = []
    for key, cnt in cache.items():
        out.append(f"{key} {cnt}")
        to_remove.append(key)
        k += 1
        if k == n:
            break
    for key in to_remove:
        del cache[key]
    print(" ".join(out))

def main():
    data = sys.stdin.read().splitlines()
    if not data:
        return
    # 第 1 行是限流参数 n
    n_line = data[0].strip()
    n = int(n_line) if n_line else 0

    cache = OrderedDict()

    # 从第 2 行开始逐行处理（包括可能的空行）
    for i in range(1, len(data)):
        line = data[i].rstrip("\n")
        # 空行：不加入任何字符串，直接触发一次 emit
        tokens = line.split() if line.strip() != "" else []
        process_line(cache, tokens)
        emit(cache, n)

if __name__ == "__main__":
    main()

Java

// 题意：LinkedHashMap 维护插入顺序；每行加入后，输出并移除至多 n 个最早键
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.io.IOException;
import java.util.LinkedHashMap;
import java.util.Map;
import java.util.ArrayList;
import java.util.List;

public class Main {

    // 将本行 tokens 写入缓存：新词保持顺序，旧词计数+1
    private static void processLine(LinkedHashMap<String, Integer> cache, String[] tokens) {
        for (String t : tokens) {
            if (t.length() == 0) continue;
            cache.put(t, cache.getOrDefault(t, 0) + 1);
        }
    }

    // 从缓存按顺序取出至多 n 个不同字符串并删除
    private static void emit(LinkedHashMap<String, Integer> cache, int n) {
        if (n == 0 || cache.isEmpty()) {
            System.out.println("null");
            return;
        }
        StringBuilder sb = new StringBuilder();
        List<String> toRemove = new ArrayList<>();
        int k = 0;
        for (Map.Entry<String, Integer> e : cache.entrySet()) {
            sb.append(e.getKey()).append(' ').append(e.getValue()).append(' ');
            toRemove.add(e.getKey());
            k++;
            if (k == n) break;
        }
        for (String key : toRemove) {
            cache.remove(key);
        }
        // 删除末尾空格
        if (sb.length() > 0 && sb.charAt(sb.length() - 1) == ' ') sb.setLength(sb.length() - 1);
        System.out.println(sb.toString());
    }

    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in, "UTF-8"));
        String first = br.readLine();
        if (first == null) return;
        first = first.trim();
        int n = first.isEmpty() ? 0 : Integer.parseInt(first);

        LinkedHashMap<String, Integer> cache = new LinkedHashMap<>();

        String line;
        while ((line = br.readLine()) != null) {
            // 注意：需要保留空行行为。空行表示本轮不加入新字符串
            String trimmed = line.trim();
            if (trimmed.isEmpty()) {
                // 无 token，直接 emit
                emit(cache, n);
            } else {
                // 使用默认分隔（空白），多空格也能正常拆分
                String[] tokens = trimmed.split("\\s+");
                processLine(cache, tokens);
                emit(cache, n);
            }
        }
    }
}

C++

// 题意：使用 list 维持顺序，unordered_map 记录次数和对应迭代器，实现 O(1) 计数与删除
#include <bits/stdc++.h>
using namespace std;

struct Node {
    string key;
    int cnt;
};

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    string firstLine;
    if (!getline(cin, firstLine)) return 0;
    // 读取 n（空或不合法视为 0，题面保证合法，此处稳妥处理）
    int n = 0;
    {
        string s = firstLine;
        // 去两端空白
        auto l = s.find_first_not_of(" \t\r\n");
        if (l != string::npos) {
            auto r = s.find_last_not_of(" \t\r\n");
            s = s.substr(l, r - l + 1);
            if (!s.empty()) n = stoi(s);
        }
    }

    // list 维护顺序，map: key -> (次数, 迭代器)
    list<Node> lst;
    unordered_map<string, list<Node>::iterator> mp;
    mp.reserve(4096);

    auto process_line = [&](const vector<string>& tokens) {
        for (const string& t : tokens) {
            if (t.empty()) continue;
            auto it = mp.find(t);
            if (it == mp.end()) {
                lst.push_back({t, 1});
                auto iter = lst.end(); --iter;
                mp.emplace(t, iter);
            } else {
                it->second->cnt += 1; // 仅计数+1，不改变顺序
            }
        }
    };

    auto emit = [&]() {
        if (n == 0 || lst.empty()) {
            cout << "null\n";
            return;
        }
        int k = 0;
        ostringstream oss;
        while (k < n && !lst.empty()) {
            auto it = lst.begin();
            oss << it->key << ' ' << it->cnt;
            lst.erase(it);
            mp.erase(oss.str().substr(0, oss.str().find(' '))); // 不能这样取 key，会错！
            // 修正：在 erase 前保存 key
        }
    };

    // 由于上面 emit 写到一半，做一次完整且安全的实现：
    auto emit_safe = [&]() {
        if (n == 0 || lst.empty()) {
            cout << "null\n";
            return;
        }
        int k = 0;
        ostringstream oss;
        bool first = true;
        vector<string> keys_to_remove;
        auto it = lst.begin();
        while (k < n && it != lst.end()) {
            if (!first) oss << ' ';
            first = false;
            oss << it->key << ' ' << it->cnt;
            keys_to_remove.push_back(it->key);
            ++k;
            ++it;
        }
        // 删除前 n 个
        for (int i = 0; i < (int)keys_to_remove.size(); ++i) {
            const string& key = keys_to_remove[i];
            auto mit = mp.find(key);
            if (mit != mp.end()) {
                lst.erase(mit->second);
                mp.erase(mit);
            }
        }
        cout << oss.str() << "\n";
    };

    string line;
    while (getline(cin, line)) {
        // 去除结尾换行，保留空行
        string trimmed = line;
        // 判断是否全是空白
        bool allspace = true;
        for (char c : trimmed) {
            if (!isspace((unsigned char)c)) { allspace = false; break; }
        }
        if (allspace) {
            // 空行：直接输出一次
            emit_safe();
        } else {
            // 按空白切分
            vector<string> tokens;
            {
                istringstream iss(trimmed);
                string tok;
                while (iss >> tok) tokens.push_back(tok);
            }
            process_line(tokens);
            emit_safe();
        }
    }
    return 0;
}

题目内容

有一个故障字符串序列由多行组成，每一行内有多个字符串，分别用空格隔开。现需要对这个字符串序列进行限流显示处理，显示规则如下:

1.输入的第一行为一个数字，表示限流参数 $n$

2.从第 $2$ 行开始为要处理的字符串数据，我们需要将每一行数据流入一个缓存控制器,缓存中的信息包括字符串和其个数信息

3.每行输入数据中的字符串可能在缓存中有重复，如果有重复需要在缓存中对字符串的个数 $+1$

4.每一行流入后需要从当前缓存中取出最早的数据进行输出，取出的数据上限为限流参数 $n$ ，如果数据未取完将继续保存在缓存中，取出的数据将从缓存中删除，后续缓存的相同字符串将重新开始计数

输入描述

输入的第一行为限流个数 $n$ ，$n$ 的范围为 $[0,100],n=0$ 表示每次输入后不输出缓存中的数据

输入的第 $2$ 行之后为要处理的数据，每行的字符串用空格隔开

每行输入的字符串个数最大为 $200$ 个，最大输入行数为 $1000$ 行

输出描述

输入的第 $2$ 行开始每一行对应一行输出信息，每行输出格式为字符串和出现的个数，用空格隔开。

当缓存没有数据输出时，输出 $null$

样例1

输入

5
abc a b c

ad bc

输出

abc 1 a 1 b 1 c 1
null
ad 1 bc 1

说明

限制单次输出 $5$ 个不同字符串

第一行输入为 $abc$ $a$ $b$ $c$ ，输入后缓存是 $abc$ $a$ $b$ $c$ ,次数均为 $1$

因此第一行输出是 $abc$ $1$ $a$ $1$ $b$ $1$ $c$ $1$

第 $2$ 行输入为空行，之前缓存为空，输入后缓存是空，因此第 $2$ 行输出为 $null$

第 $3$ 行输入为 $ad$ $bc$ ，之前缓存为空，输入后缓存是 $ad$ $bc$ , 次数均为 $1$ ,因此第 $3$ 行输出为 $ad$ $1$ $bc$ $1$

所以最终输出为：

$abc$ $1$ $a$ $1$ $b$ $1$ $c$ $1$

$null$

$ad$ $1$ $bc$ $1$

样例2

输入

5
hard_bad dbms_error r_los low_power
mem_over mem_bad bit_error low_power storage_fail
hard_bad dbms_error r_los
hard_bad dbms_error r_los power_off

输出

hard_bad 1 dbms_error 1 r_los 1 low_power 1
mem_over 1 mem_bad 1 bit_error 1 low_power 1 storage_fail 1
hard_bad 1 dbms_error 1 r_los 1
hard_bad 1 dbms_error 1 r_los 1 power_off 1

说明

第一行 $5$ 表示每次最多输出 $5$ 个字符串信息

第 $2$ 行输入为 $4$ 个不同的字符串，流入缓存后，缓存只有 $4$ 个字符串，全部输出，次数均为 $1$

第 $2$ 次输入为有 $8$ 个不同字符串，流入缓存后，缓存只有 $8$ 个字符串，输出前 $5$ 个，次数均为 $1$ ,

输出后缓存中有 $hard\_bad$ $dbms\_error$ $r\_los$ , 次数都是 $1$

第 $3$ 次输入时 $hard\_bad,dbms\_error,r\_los$ 缓存中存在，计数加 $1$ , 输入后出现次数为 $2$ ，最后的 $power\_off$ 出现次数为 $1$ ，全部输出