解题思路

本题要求从多个字符串中提取字符并构造一个长度为 K 的新字符串，且要使得构造出来的字符串字典序最小。具体的步骤可以分为以下几个阶段：

1. 问题分析

我们有 N 个字符串，每个字符串中有一个最大提取字符的限制 X_i。我们需要从每个字符串中提取字符并构成一个新字符串，使得新字符串的字典序最小，且总字符数为 K。

2. 核心思路

为了确保字典序最小，我们应该尽量优先选取字母较小的字符。因此，我们首先要从每个字符串中提取出字母并按字典序排列，然后在构建目标字符串时，每次都选取当前字母中最小的一个。

3. 具体步骤

1. 解析输入：首先读入 N 和 K，然后逐个读入每个字符串及其对应的 X_i 值。
2. 字符提取：每个字符串中，我们可以提取出最多 X_i 个字符。提取时，应先对字符串排序，这样能确保提取的是字典序最小的字符。
3. 维护字符池：使用一个优先队列（最小堆）来维护当前所有字符串中待选的字符。每次从堆中取出字典序最小的字符并加入结果中。
4. 构造结果：重复从堆中取字符直到构成一个长度为 K 的新字符串。

4. 算法实现

1. 最小堆：每次从堆中取出最小字符，保证了字典序最小。
2. 优先选择小字符：通过优先队列可以确保在每次提取字符时总是选择当前最小的字符。

5. 复杂度分析

• 构造每个字符串的字符池时，我们需要对每个字符串排序，时间复杂度为 O(|S_i| log |S_i|)。假设字符串总字符数为 M，那么排序总的时间复杂度为 O(M log M)。
• 维护一个优先队列来管理字符池，每次从队列中取出字符的时间复杂度为 O(log N)。
• 总的时间复杂度为 O(M log M + K log N)，其中 M 是所有字符串的字符总数，N 是字符串的个数，K 是目标字符串的长度。

Python代码

import heapq

def solve(N, K, strings):
    # 用来存储从每个字符串中提取出的字符
    heap = []
    
    # 处理每个字符串
    for S, X in strings:
        # 把每个字符串排序，这样我们可以方便地按字典序选取字符
        sorted_chars = sorted(S)
        # 只取前 X 个字符，加入堆
        for c in sorted_chars[:X]:
            heapq.heappush(heap, c)
    
    # 构造最终的字符串
    result = []
    for _ in range(K):
        # 取出字典序最小的字符
        result.append(heapq.heappop(heap))
    
    return ''.join(result)

# 输入
N, K = map(int, input().split())
strings = []
for _ in range(N):
    S, X = input().split()
    strings.append((S, int(X)))

# 输出结果
print(solve(N, K, strings))

Java代码

import java.util.*;

public class Main {
    public static String solve(int N, int K, List<Pair<String, Integer>> strings) {
        // 用来存储从每个字符串中提取出的字符
        PriorityQueue<Character> minHeap = new PriorityQueue<>();
        
        // 处理每个字符串
        for (Pair<String, Integer> pair : strings) {
            String S = pair.getKey();
            int X = pair.getValue();
            char[] sortedChars = S.toCharArray();
            Arrays.sort(sortedChars);
            // 只取前 X 个字符，加入堆
            for (int i = 0; i < X; i++) {
                minHeap.add(sortedChars[i]);
            }
        }
        
        // 构造最终的字符串
        StringBuilder result = new StringBuilder();
        for (int i = 0; i < K; i++) {
            result.append(minHeap.poll());
        }
        
        return result.toString();
    }

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int N = sc.nextInt();
        int K = sc.nextInt();
        sc.nextLine(); // Consume the newline
        
        List<Pair<String, Integer>> strings = new ArrayList<>();
        for (int i = 0; i < N; i++) {
            String s = sc.next();
            int X = sc.nextInt();
            strings.add(new Pair<>(s, X));
            sc.nextLine(); // Consume the newline
        }

        // 输出结果
        System.out.println(solve(N, K, strings));
    }
}

// Pair class to store string and limit X
class Pair<K, V> {
    private K key;
    private V value;
    
    public Pair(K key, V value) {
        this.key = key;
        this.value = value;
    }
    
    public K getKey() {
        return key;
    }
    
    public V getValue() {
        return value;
    }
}

C++代码

#include <iostream>
#include <vector>
#include <queue>
#include <algorithm>

using namespace std;

string solve(int N, int K, vector<pair<string, int>>& strings) {
    // 用来存储从每个字符串中提取出的字符
    priority_queue<char, vector<char>, greater<char>> minHeap;
    
    // 处理每个字符串
    for (auto& pair : strings) {
        string S = pair.first;
        int X = pair.second;
        sort(S.begin(), S.end());
        // 只取前 X 个字符，加入堆
        for (int i = 0; i < X; i++) {
            minHeap.push(S[i]);
        }
    }
    
    // 构造最终的字符串
    string result;
    for (int i = 0; i < K; i++) {
        result += minHeap.top();
        minHeap.pop();
    }
    
    return result;
}

int main() {
    int N, K;
    cin >> N >> K;
    
    vector<pair<string, int>> strings(N);
    for (int i = 0; i < N; i++) {
        string S;
        int X;
        cin >> S >> X;
        strings[i] = {S, X};
    }
    
    // 输出结果
    cout << solve(N, K, strings) << endl;
    
    return 0;
}

题目内容

多多在玩一个游戏，他想要从一堆字符串中构造出一个新的字符串，具体规则如下：

给定 $N$ 个字符串，多多可以从第 $i$ 字符串中提取出最多 $X_i$ 个字符，被取出字符可以按任意顺序拼接成一个长度为 $K$ 的新字符串 $T$，但多多希望这个字符串的字典序尽可能的小。

请问多多最终得到的新字符串是什么?

输入描述

第一行，两个整数 $N$ 和 $K$，表示有 $N$ 字符串以及目标串 $T$ 的长度。

接下来 $N$ 行，第 $i$ 行有一个字符串和一个整数：$S_i，X_i$。

$S_i$ 是第 $i$ 个字符串

$X_i$ 是要求第 $i$ 个字符串取出的字符个数

$1 <= N <= 1000$

$1 <= |S_i| <= 1000$

$0 <= X_i <= |S_i|$

$0 <= K <= \sum X_i<= 1000000$

输出描述

一个字符串 $T$

示例1

输入

2 3
abb 2
ccaa 1

输出

aab

说明

从第 $2$ 个字符串中取出 $a$，第 $1$ 个字符串中取出 $a$ 和 $b$，拼接成 $aab$ 的字典序最小。

示例2

输入

3 5
aaa 0
bab 2
aaa 3

输出

aaaab