-
Notifications
You must be signed in to change notification settings - Fork 94
/
Flowers.py
52 lines (40 loc) · 1.53 KB
/
Flowers.py
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
"""
You and your K-1 friends want to buy N flowers. Flower number i has cost ci. Unfortunately the seller does not want just
one customer to buy a lot of flowers, so he tries to change the price of flowers for customers who have already bought
some flowers. More precisely, if a customer has already bought x flowers, he should pay (x+1)*ci dollars to buy flower
number i.
You and your K-1 friends want to buy all N flowers in such a way that you spend the least amount of money. You can buy
the flowers in any order.
Input:
The first line of input contains two integers N and K (K <= N). The next line contains N space separated positive
integers c1,c2,...,cN.
Output:
Print the minimum amount of money you (and your friends) have to pay in order to buy all N flowers.
"""
__author__ = 'Danyang'
class Solution(object):
def solve(self, cipher):
"""
Array math
Sort the costs
Group the costs
:param cipher: the cipher
"""
N, K, C = cipher
C.sort(reverse=True)
group_cnt = N / K + 1 # 1 is the last remaining group
total_cost = 0
for i in xrange(group_cnt):
unit_cost = i + 1
total_cost += unit_cost * sum(C[i * K:(i + 1) * K])
return total_cost
if __name__ == "__main__":
import sys
f = open("1.in", "r")
# f = sys.stdin
N, K = map(int, f.readline().strip().split(' '))
C = map(int, f.readline().strip().split(' '))
cipher = N, K, C
# solve
s = "%s\n" % (Solution().solve(cipher))
print s,