PROBLEM LINK:
Practice
Contest: Division 1
Contest: Division 2
Contest: Division 3
Contest: Division 4
Author: raysh07
Tester: sushil2006
Editorialist: iceknight1093
DIFFICULTY:
Cakewalk
PREREQUISITES:
None
PROBLEM:
There are N items in a shop. The i-th item has cost C_i.
Find the cost of buying the K most expensive items.
EXPLANATION:
This is a simple implementation task, with the small constraints allowing for many solutions.
A couple of methods that work are:
- To buy the K most expensive items, we can buy the single most expensive item and then delete it from the array; repeat this K times and we’ll end up with what we need.
Finding the most expensive item and deleting it can be done with a loop, so this method has a complexity of \mathcal{O}(N\cdot K) since it’s repeated K times. - Alternately, sort the array C in ascending order, and then just add up the last K elements since there are the most expensive elements.
Sorting can be done in \mathcal{O}(N^2), \mathcal{O}(N\log N), or even \mathcal{O}(N + 100) depending on the method you choose - the constraints are low enough that any of them will be fast enough.
TIME COMPLEXITY:
Between \mathcal{O}(N) and \mathcal{O}(N^2) per testcase.
CODE:
Editorialist's code (PyPy3)
for _ in range(int(input())):
n, k = map(int, input().split())
c = list(map(int, input().split()))
c.sort()
ans = 0
for i in range(k):
ans += c[n-1-i]
print(ans)