프로그램 명: coci_razlika
제한시간: 1 초
[요약]
N 개의 정수가 주어진 나열 V 가 주어진다.
문제는 이 나열로 부터 정확하게 K 개를 제거 후 남은 숫자 중 차이의 최댓값을 M , 최솟값을 m 이라하면
최소 M + m 을 출력하는 것이다.
Mirko's newest math homework assignment is a very difficult one! Given a sequence, V, of N integers,
remove exactly K of them from the sequence. Let M be the largest difference of any two remaining
numbers in the sequence, and m the smallest such difference. Select the K integers to be removed from
V in such a way that the sum M + m is the smallest possible. Mirko isn't very good at math, so he has
asked you to help him!
입력
-
The first line of input contains two positive integers, N (3 ≤ N ≤ 1 000 000) and K (1 ≤ K ≤ N - 2).
-
The second line of input contains N space-separated positive integers , the sequence V (-5 000 000 ≤ Vi ≤ 5 000 000).
출력
The first and only line of output must contain the smallest possible sum M + m.
입출력 예
input
5 2
-3 -2 3 8 6
output
7
input
6 2
-5 8 10 1 13 -1
output
13
input
6 3
10 2 8 17 2 17
output
6
출처:coci/2012-2013/contest4 4번
[질/답]
[제출 현황]
[푼 후(2)]