greedy algorithms - minimizing total payment The question:

I want to buy $n$ books. In the book store there's a big sale according to which, if you buy three books, then the cheapest book in any triplet costs only 20% of its full price.  Let $c_1, c_2, …, c_n$ be the full price of the books you want to buy. 

Suggest an algorithm for minimizing your total payment. Prove its optimality and analyze its time complexity.

My algorithm:


sort the prices of the books from big to small, such that $c_1 \ge c_2 \ge ... \ge c_n $ (change the locations of the books).
each book $c_i$ if $i \% 3 = 0 $ then change its price to $c_i=0.2\cdot c_i$
return the sum of all books $\sum_{i=1}^nc_i$


Now, I'm having trouble proving that this is the optimal solution.
I want to prove that if $i\%3=0$ for $c_i$, then I have a discount on this book.

I'm having a hard time formalizing the Greedy choice property. Given an optimal solution, what happens if $c_i$ such that $i\%3=0$ is not in the optimal solution? (doesn't have a discount)?
This answer is a hint.

Assume an optimal solution exists.  Order its choices so that they agree with your algorithm's choices for as long as possible; the order after this is unimportant.  If all of them agree, then your algo picked an optimal solution, so you're done!  If not, then at look at the first group of 3 where they disagreed.  Even though you don't know exactly what an optimal solution is, you know that one exists, and you can make changes to it -- e.g. swapping some books in its ordering -- to produce a new solution.

Can you think of a way to change it in such a way that (a) it now agrees with your algo for 1 more group of 3 and (b) its score didn't get worse?  If so, then clearly you could repeat this step until...  What happens?