https://www.acmicpc.net/problem/2212
initial
I was able to solve this by thinking of the pattern
So we wanna remove the greatest distance difference for tower-1 number of times cuz we dont want our ans to be big.
Oh but the runtime error I got was if n=1 (i.e. only 1 sensor), then my lst[i]-lst[i-1] will cause runtime error cuz there is only 1 element in the list. If there is 1 sensor, answer is 0 cuz we can just place a tower on that sensor.
solution
import sys
input = sys.stdin.readline
n=int(input())
m=int(input())
lst = list(map(int,input().split()))
if n==1:
print(0)
exit()
lst.sort()
tmp = []
carry=0
for i in range(1,n):
tmp.append(lst[i]-lst[i-1])
tmp.sort(reverse=True)
for i in range(m-1):
carry+=tmp[i]
ans = lst[-1]-lst[0]-carry
print(ans)complexity
log n cuz sort?
oh it is n log n for sort loll
Time Complexity:
Sorting the original list takes O(n log(n)) time.
Sorting the differences takes O((n-1) log(n-1)) time.
The loops run in O(n) and O(m), which are smaller than the sorting steps.
Overall, the dominant factor is sorting, so the time complexity is O(n * log(n)).
Space Complexity:
The space complexity is O(n) for the tmp list storing the differences.
