e591 - 11264 - Coin Collector
題目描述
題目描述了 Sultan 在一個國家旅行，他想從銀行提取錢幣，並儘可能收集到最多種類的硬幣。銀行會優先給予面額最大的、小於等於剩餘金額的硬幣。題目要求計算 Sultan 在一次提款中最多可以獲得多少種類不同的硬幣。
解題思路
這題可以使用貪心演算法解決。由於銀行總是優先給予面額最大的硬幣，因此 Sultan 應該按照硬幣面額由大到小的順序考慮。
- 首先，對硬幣面額進行排序。
- 然後，從最大的硬幣開始，如果當前硬幣面額小於等於剩餘金額，則取出該硬幣，並更新剩餘金額和收集到的硬幣種類數量。
- 重複步驟 2，直到剩餘金額為 0 或所有硬幣都已考慮過。
程式碼中，total 記錄了已收集的硬幣總價值，ans 記錄了已收集的硬幣種類數量，a 記錄了上次收集的硬幣面額。每次迭代，如果當前硬幣 b 大於 total，則表示可以新增一種硬幣，ans 加 1，total 更新為 total + b，a 更新為 b。如果 b 不大於 total 但大於 a，則表示可以替換掉之前收集的較小面額硬幣，total 更新為 total + (b - a)，a 更新為 b。
複雜度分析
- 時間複雜度: O(n log n) (主要來自排序)
- 空間複雜度: O(1)
程式碼
#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 <stdio.h>
inline int read(){
int a(0);
char c('0');
while(c>='0'){
a=(a<<3)+(a<<1)+c-'0';
c=getchar_unlocked();
}
return a;
}
inline void write(int x) {
int stk[9],*ptr(&stk[0]);
while(x){*ptr=x%10;x/=10;++ptr;}
while(--ptr>=(&stk[0])){putchar_unlocked(*ptr+'0');}
}
int main(){
int t=read(),n,a,b,total,ans;
while(t--){
n=read();
ans=0;total=0;a=0;
while(n--){
b=read();
if(b>total){
++ans;
total+=b;
a=b;
}
else if(b>a){
total+=(b-a);
a=b;
}
}
write(ans);
putchar_unlocked('\n');
}
}