Shopaholic

From Progteam

Revision as of 00:26, 29 April 2009 by Nina (Talk | contribs)
(diff) ← Older revision | Latest revision (diff) | Newer revision → (diff)
Jump to: navigation, search


Checkmark.jpg This problem has been solved by Eric.



Shopaholic
Problem Number 3637
Sorter: Eric
Source: Nordic 2007
Link: http://acm.pku.edu.cn/JudgeOnline/problem?id=3637




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


Contents

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.
  4. Add every third prices.


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++)
			prices.add(in.nextInt());
		
		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);
	}
}


Additional Remarks

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

//ADD THE DISCOUNTS!
for(int i=numItems - 3; i>-1; i-=3) {
	sum = sum + items.get(i);
}
Personal tools