i918 - 12626 - I ❤ Pizza
題目描述
題目要求計算給定一組食材，最多可以製作多少個瑪格麗塔披薩。瑪格麗塔披薩需要 1 個 'M', 3 個 'A', 2 個 'R', 1 個 'G', 1 個 'I', 和 1 個 'T'。
解題思路
對於每組測試資料，統計輸入字串中各個字母的出現次數。然後，分別計算可以製作的披薩數量，基於 'M', 'A', 'R', 'G', 'I', 'T' 的數量。最後，取這些數量中的最小值，即為可以製作的瑪格麗塔披薩的最大數量。使用貪心策略，盡可能多地利用現有食材製作披薩。
複雜度分析
- 時間複雜度: O(n) (n 是輸入字串的長度，因為需要遍歷字串一次來統計字母出現次數)
- 空間複雜度: O(1) (使用固定大小的陣列
c[26]儲存字母計數，大小不隨輸入大小變化)
程式碼
#include <iostream>
using namespace std;
int n;
string s;
int main(){
cin.tie(0); ios::sync_with_stdio(false);
cin >> n;
for(int i=0;i<n;++i){
cin >> s;
int c[26]={},ans=1e9;
for(int j=0;j<s.size();++j)
++c[s[j]-'A'];
ans=min(ans,c['M'-'A']);
ans=min(ans,c['A'-'A']/3);
ans=min(ans,c['R'-'A']/2);
ans=min(ans,c['G'-'A']);
ans=min(ans,c['I'-'A']);
ans=min(ans,c['T'-'A']);
cout << ans << '\n';
}
}