#P2887. 第1题-多多的游戏
-
1000ms
Tried: 94
Accepted: 37
Difficulty: 3
所属公司 :
拼多多
时间 :2025年4月20日-算法岗
-
算法标签>排序堆
第1题-多多的游戏
解题思路
本题要求从多个字符串中提取字符并构造一个长度为 K 的新字符串,且要使得构造出来的字符串字典序最小。具体的步骤可以分为以下几个阶段:
1. 问题分析
我们有 N 个字符串,每个字符串中有一个最大提取字符的限制 X_i。我们需要从每个字符串中提取字符并构成一个新字符串,使得新字符串的字典序最小,且总字符数为 K。
2. 核心思路
为了确保字典序最小,我们应该尽量优先选取字母较小的字符。因此,我们首先要从每个字符串中提取出字母并按字典序排列,然后在构建目标字符串时,每次都选取当前字母中最小的一个。
3. 具体步骤
- 解析输入:首先读入
N和K,然后逐个读入每个字符串及其对应的X_i值。 - 字符提取:每个字符串中,我们可以提取出最多
X_i个字符。提取时,应先对字符串排序,这样能确保提取的是字典序最小的字符。 - 维护字符池:使用一个优先队列(最小堆)来维护当前所有字符串中待选的字符。每次从堆中取出字典序最小的字符并加入结果中。
- 构造结果:重复从堆中取字符直到构成一个长度为
K的新字符串。
4. 算法实现
- 最小堆:每次从堆中取出最小字符,保证了字典序最小。
- 优先选择小字符:通过优先队列可以确保在每次提取字符时总是选择当前最小的字符。
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 字符串中提取出最多 Xi 个字符,被取出字符可以按任意顺序拼接成一个长度为 K 的新字符串 T,但多多希望这个字符串的字典序尽可能的小。
请问多多最终得到的新字符串是什么?
输入描述
第一行,两个整数 N 和 K,表示有 N 字符串以及目标串 T 的长度。
接下来 N 行,第 i 行有一个字符串和一个整数:Si,Xi。
Si 是第 i 个字符串
Xi 是要求第 i 个字符串取出的字符个数
1<=N<=1000
1<=∣Si∣<=1000
0<=Xi<=∣Si∣
0<=K<=∑Xi<=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