e313 - 最少相異字母
題目描述
題目要求從 N 個字串中找出含有最少相異字母的字串。如果有多個字串具有最少的相異字母數，則選擇字典序最小的字串。
解題思路
這個問題可以使用貪心策略解決。遍歷所有字串，對於每個字串，計算其中相異字母的數量。維護一個變數 ma 記錄目前找到的最少相異字母數，以及一個變數 ans 記錄對應的字串。
每次遇到一個新的字串，計算其相異字母數 ct。如果 ct 小於 ma，則更新 ma 和 ans。如果 ct 等於 ma，則比較當前字串和 ans 的字典序，選擇字典序較小的字串作為新的 ans。
最後，輸出 ans。
複雜度分析
- 時間複雜度: O(N * M)，其中 N 是字串的數量，M 是字串的平均長度。
- 空間複雜度: O(1)，因為使用的額外空間是固定的，不隨輸入大小變化。
程式碼
#include <iostream>
using namespace std;
int n,ma;
string s,ans;
int main(){
cin.tie(0); ios::sync_with_stdio(false);
cin >> n;
for(int i=0;i<n;++i){
cin >> s;
int ct=0;
bool x[26]={};
for(int j=0;j<s.size();++j)
x[s[j]-'A']=1;
for(int j=0;j<26;++j)
ct+=x[j];
if(i==0||ct<ma||(ct==ma&&s<ans)){
ans=s;
ma=ct;
}
}
cout << ans;
}