高中生程式解題系統 d150: 11369 - Shopaholic－資工趴趴熊的小天地

Content

林希是個購物狂。每次只要有買二送一的折扣，她就像瘋了一樣要買下店裡所有的商品。你已經放棄治療她的病了，但是想減少她的支出。

你知道買二送一所送的一定是結帳商品中最便宜的那幾樣。比如說，你的朋友拿了價值為400, 350, 300, 250, 200, 150, 及 100 的七樣商品到櫃枱去結帳，她就得付 1500 元。她省下了最便宜的兩樣商品的價錢，也就是 250 元。如果她分三次去結帳，她可以省下更多的錢。比如說，她先拿400, 300 和 250 的去結，第一次就可以省下 250 元。第二次她只拿 150 元的去結，沒有折扣。但是第三次她拿350, 200, 和 100 的去結，又省了 100 元，總共省下了 350 元。

你的工作便是找出林希最多可以省多少錢。

Input

第一行是測試筆數 1 ≤ t ≤ 20。每筆測試有兩行輸入。第一行是林希買的商品數 1 ≤ n ≤ 20000。下一行則是這些商品的價格 1 ≤ pi ≤ 20000。

Output

每個測試，輸出一行，印出如果林希適當地分次結帳時所能省下的最大金額。

Sample Input #1

1
6
400 100 200 350 300 250

Sample Output #1

"""
解題思路:
1先把他"由大到小排序"
取第2個，第5個，第8個....以此類推
"""

python:

"""
解題思路:
1先把他"由大到小排序"
取第2個，第5個，第8個....以此類推
"""
t=int(input())
for i in range(t):
    n=int(input())
    for j in range(n):
        pi=[int(x) for x in input().split()]
        pi.sort(reverse=True)
        #print(pi)
        ans=0
        for  k in range(2,len(pi),3):
            ans+=pi[k]
        print(ans)

C++:

#include <iostream> 
#include <algorithm> 
using namespace std;
bool cmp(int a,int b){
	return a>b;
}


int main(){
	//ios::sync_with_stdio(0);
	//cin.tie(0);
	int t,n;
	cin>>t;
	while(t--){
		cin>>n;
		int arr[n];
		for(int i=0;i<n;i++){
			cin>>arr[i];
		}
		sort(arr,arr+n,cmp);
		int ans=0;
		for(int i=2;i<n;i+=3){
			ans+=arr[i];
		}
		cout<<ans<<"\n";
	}
	return 0;
}