d150 - 11369 - Shopaholic
題目描述
題目描述了林希購物時遇到買二送一的優惠，要求計算她能透過適當分次結帳，最大化省下的金額。核心在於將商品價格排序後，每次結帳盡可能利用買二送一的優惠，省下最便宜的商品價格。
解題思路
解題思路是先將所有商品價格由高到低排序。然後，每次從排序後的列表中取出三件商品進行結帳。在每三次結帳中，最便宜的商品會被免費送出，因此可以省下該商品的价格。重複此過程直到所有商品都被結帳。由於商品已排序，因此每次取出的最便宜商品價格都是當前可選商品中最便宜的。
複雜度分析
- 時間複雜度: O(n log n)
- 空間複雜度: O(n)
程式碼
#include <iostream>
#include <algorithm>
using namespace std;
bool cmp(int a,int b){
return a>b;
}
int main(){
int t;
cin >> t;
while(t--){
int a[t]={0},sum=0;
for(int i=0;i<t;i++)
cin >> a[i];
sort(a,a+t,cmp);
for(int i=2;i<t;i+=3)
sum+=a[i];
cout << sum << "\n";
}
}