Sorting 0/1

Lesson 15 of 21

Sorting

Sort by any key you choose, then scan the sorted values; and see what sorting costs.

Part 1 of 7 Sorting by a key

Sorting by a key

You have already sorted a few times in this course: sorted put the letters of a word in order, and it put a dictionary's keys in order. Both times the values were compared in their usual order: numbers from smallest to largest, and strings by character code, which for lowercase words is dictionary order.

Often you want a different order. A leaderboard lists players from the most wins to the fewest. A to-do list goes by deadline. A word game might want the shortest words first. The values are the same in each case; what changes is the rule for which one comes first. In this lesson you'll learn how to give the sort that rule, and then what a list in the right order lets you do: answer questions about repeated and nearby values in one pass, and choose the order in which to do a set of jobs.

Take four words, ['mango', 'fig', 'banana', 'pear'], that you want from shortest to longest. sorted(words) compares the words themselves, so it gives alphabetical order. You need it to compare their lengths instead. That is what a key is for: a function of one item that sorted calls once on each item. The items are then sorted by the values it returns. With key=len, the four words are sorted by the lengths 5, 3, 6 and 4.

sorted(items) returns a new sorted list and leaves items as it was, while items.sort() sorts the list itself. Both take a key, and reverse=True turns the order around, so that the longest words come first. This program sorts the words three ways:

Sorting words three ways

Sign up to run
words = ['mango', 'fig', 'banana', 'pear']
print(sorted(words))
print(sorted(words, key=len))
print(sorted(words, key=len, reverse=True))
Python details

key=len passes the function len itself, with no parentheses; sorted does the calling. A key can be any one-argument function: a built-in such as len, a function you wrote with def, or a lambda. Uppercase letters come before lowercase ones, and key=lambda w: w.lower() sorts words as if they were all lowercase.

Sorting from largest to smallest puts the largest items first, and this problem asks for the largest few:

Snuke has NN sticks, and the ii-th stick has length lil_i. He makes a toy by joining KK of the sticks, and the toy's length is the sum of their lengths. Print the largest possible length of the toy.

Constraints

  • 1≤K≤N≤501 \le K \le N \le 50
  • 1≤li≤501 \le l_i \le 50

Sample 1 · Input

5 3
1 2 3 4 5

Output

12

Sample 2 · Input

15 14
50 26 27 21 41 7 42 35 7 5 5 36 39 1 45

Output

386

In the first sample, 3 of the sticks 1 to 5 are chosen, and the best choice is the three longest, 3+4+5=123 + 4 + 5 = 12. That holds in general: replacing any chosen stick with a longer unchosen one makes the toy longer, so the answer is the sum of the KK longest sticks. Once the lengths are sorted from longest to shortest, those are the first KK.

Summing the K longest sticks

Sign up to run
n, k = map(int, input().split())
lengths = list(map(int, input().split()))
lengths.sort(reverse=True)
print(sum(lengths[:k]))
Python details

lengths[:k] is a slice holding the first k elements, and sum adds them.