d804 - 好餓
題目描述
題目描述了在有限種類的餐點中，找到最少份數的餐點組合，使得總飽足感達到或超過指定值。如果無法達到指定飽足感，則輸出 "OAQ"。
解題思路
此題可以使用貪心演算法解決。首先，將所有餐點的飽足感進行排序，從大到小。然後，從飽足感最高的餐點開始，依次將它們加入組合中，直到總飽足感達到或超過目標值。如果遍歷完所有餐點後，總飽足感仍然不足，則輸出 "OAQ"。
複雜度分析
- 時間複雜度: O(n log n) (主要來自排序)
- 空間複雜度: O(n) (用於儲存餐點的飽足感)
程式碼
#pragma GCC optimize("Ofast,unroll-loops,no-stack-protector,fast-math")
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")
#include <iostream>
#include <algorithm>
using namespace std;
int a[100001],n,full;
inline int read(){
int a(0);
char c('0');
while(c>='0'){
a=(a<<3)+(a<<1)+c-'0';
c=getchar_unlocked();
}
return a;
}
int main(){
while(cin >> n >> full){
int h=0;
a[0]=read();
for(int i=0;i<n;++i)
a[i]=read();
sort(a,a+n);
for(int i=n-1;i>=0;--i){
h+=a[i];
if(h>=full){
cout << n-i << "\n";
break;
}
}
if(h<full){
cout << "OAQ\n";
}
}
}