UVa 11369 – Shopaholic
Linxi is a shopping fanatic. Whenever there's a "buy two, get one free" discount, she goes crazy and wants to buy everything in the store. You have given up trying to cure her obsession, but you want to help reduce her spending.
You know that with the "buy two, get one free" offer, the items given for free are always the cheapest ones among those being checked out. For example, if your friend takes items priced at 400, 350, 300, 250, 200, 150, and 100 to the counter, she will have to pay 1500. She saves the cost of the two cheapest items, which is 250. However, if she checks out in three separate transactions, she can save more money. For instance, if she first checks out the 400, 300, and 250 items, she saves 250 on the first transaction. The second transaction includes only the 150 items, which doesn’t qualify for a discount. In the third transaction, she checks out the 350, 200, and 100 items, saving 100. In total, she saves 350.
Your task is to find out the maximum amount of money Linxi can save.
Sample Inputs/Outputs
| Sample Input(s) | Sample Output(s) |
|---|---|
| The first line contains the number of test cases, where 1 ≤ T ≤ 20. Each test case consists of two lines of input. The first line contains the number of items Linxi buys, where 1 ≤ N ≤ 20,000. The next line contains the prices of these items, where 1 ≤ Pi ≤ 20,000. | For each test case, output a single line containing the maximum amount of money Linxi can save by appropriately checking out items in separate transactions. |
| 1 6 400 100 200 350 300 250 | 400 |
Thought Process
Store the price of each item in a vector and then use sorting.
Run a for loop from the largest to the smallest, in increments of three, and add the price of the item at the current position minus 2 to the answer.
Sample Code－ZeroJudge D150: Shopaholic
#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;
int main() {
cin.sync_with_stdio(0);
cin.tie(0);
int T;
cin >> T;
for (int i = 0; i<T; i++)
{
int N;
cin >> N;
vector<int>num;
for (int j = 0; j<N; j++)
{
int tmp;
cin >> tmp;
num.push_back(tmp);
}
sort(num.begin(), num.end());
int ans = 0;
for (int j = N-1; j>=0; j--)
{
if (j - 2 < 0) break;
else
{
ans += num[j-2];
j -= 2;
}
}
cout << ans << "\n";
}
}
//ZeroJudge D150
//Dr. SeanXD