j033 - 11900 - Boiled Eggs
題目描述
題目描述了三個麻煩製造者在沒有瓦斯爐的情況下，嘗試用微波爐煮雞蛋。他們有n個雞蛋，每個雞蛋都有重量，並且有兩個限制：碗裡雞蛋的數量不能超過P個，碗裡雞蛋的總重量不能超過Q克。目標是找出他們可以在一次煮蛋中煮的最大雞蛋數量。
解題思路
解題思路是使用貪心演算法。首先，將雞蛋按照重量從小到大排序。然後，從重量最小的雞蛋開始，依次將雞蛋放入碗中，直到碗裡雞蛋的數量達到P個或者碗裡雞蛋的總重量達到Q克。最後，輸出碗裡雞蛋的數量，但不能超過P個。
複雜度分析
- 時間複雜度: O(n log n)
- 空間複雜度: O(n)
程式碼
#include <iostream>
#include <algorithm>
using namespace std;
int main(){
cin.tie(0); ios::sync_with_stdio(0);
int t,n,p,q,a[30];
cin >> t;
for(int ca=1;ca<=t;++ca){
cin >> n >> p >> q;
int s=0,ans=0;
for(int i=0;i<n;++i)
cin >> a[i];
sort(a,a+n);
for(int i=0;i<n;++i)
if(s+a[i]<=q){
++ans;
s+=a[i];
}
cout << "Case " << ca << ": " << min(ans,p) << "\n";
}
}