# Shopaholic

(diff) ← Older revision | Latest revision (diff) | Newer revision → (diff)

 This problem has been solved by Eric.

 Sorter: Eric Nordic 2007 http://acm.pku.edu.cn/JudgeOnline/problem?id=3637

Shopaholic is problem number 3637 on the Peking University ACM site.

## Problem Information

Problem Name: Shopaholic
Problem Number on PKU: 3637
Synopsis: Maximizing the total savings on this "Buy 2 Get 1 Free" shopping spree.

## Solver Information

Solver: Eric Hong
Date: September 21, 2008

## Trivia

I tried to optimize the code after my answer got accepted. I ended up using more memory.

## General Strategy

1. Using Scanner, take the input.
2. Populate the scores into an ArrayList list.
3. Sort list in the descending order.

## Solution

import java.util.*;

public class Main
{
public static Scanner in;

public static void main(String[] args)
{
in = new Scanner(System.in);
doStuff();
}

public static void doStuff()
{
int numCase = in.nextInt();

for (int i = 0; i < numCase; i++)
solve();
}

public static void solve()
{
ArrayList<Integer> prices = new ArrayList<Integer>();
int numItem = in.nextInt();
int saving = 0;

for (int i = 0; i < numItem; i++)

Collections.sort(prices);
Collections.reverse(prices);

for (int j = 1; j <= numItem; j++)
if (j % 3 == 0)
saving += (Integer) prices.get(j - 1);

System.out.println(saving);
}
}

Memory: 8232K
Time: 1297MS

This solution may not be as efficient as it can be.

Memory: 8060K Time: 1235MS Instead of reversing the list, going backwards can save memory and running time. ooOOoo -Nina