e666 - 108 p4. 排序問題

🔗 前往 ZeroJudge 原題

題目描述

題目要求讀取一個字串 a 以及兩個整數 N 和 M。首先，將字串 a 按照字典序排序。然後，讀取 M 個整數，每個整數 N 代表字串 a 中索引為 N-1 的字元，並將這些字元依序輸出。

解題思路

本題的解題思路非常直接。首先，使用 std::sort 函數對輸入的字串進行排序。然後，迴圈讀取 M 個整數，每次讀取一個整數 N，就輸出排序後的字串 a 中索引為 N-1 的字元。由於題目要求快速輸入輸出，使用了 std::ios::sync_with_stdio(false) 和 cin.tie(NULL) 來關閉 C 和 C++ 的同步，並取消 cin 的綁定。

複雜度分析

• 時間複雜度: O(n log n + m)，其中 n 是字串的長度，m 是讀取的整數個數。排序字串的時間複雜度為 O(n log n)，迴圈讀取和輸出字元的時間複雜度為 O(m)。
• 空間複雜度: O(n)，主要用於儲存字串 a。

程式碼

#include <iostream>
#include <string>
#include <algorithm>
using namespace std;
int main(){
	std::ios::sync_with_stdio(false);
    cin.tie(NULL);
	string a;
	int N,M;
	while(cin >> N >> M >> a){
		sort(a.begin(), a.end());
		cout << endl;
		for(;M>0;M--){
			cin >> N;
			cout << a[N-1];
		}
		cout << endl;
	}
	return 0;
}