Мое решение не проходит тесты в проблеме, описанной ниже. Проходя предоставленные примеры тестовых примеров, он возвращает неправильный ответ в некоторых скрытых тестовых примерах.
Я все еще не могу выяснить проблему или найти какой-либо тестовый пример в сети.
Задача: Тренировка
Как футбольный тренер в вашей местной школе, вам было поручено выбрать команду из P учеников, представляющих вашу школу. Вы можете выбрать из N студентов. У i-го студента есть уровень квалификации Si, который является положительным целым числом, указывающим, насколько он квалифицирован.
Вы решили, что команда справедлива, если в ней ровно P учеников, и у них всех одинаковые рейтинг навыка. Таким образом, все играют как команда. Первоначально, было бы невозможно выбрать честную команду, поэтому вы будете давать некоторым студентам индивидуальные занятия. Требуется один час тренировки, чтобы повысить рейтинг мастерства любого студента на 1.
Соревновательный сезон начинается очень скоро (фактически, первый матч уже начался!), Так что вы хотели бы найти минимальное количество часов тренировки, которое вам нужно дать, прежде чем вы сможете выбрать честную команду.
Ввод
В первой строке входных данных указывается число контрольные примеры, T. T контрольные примеры следуют. Каждый тестовый пример начинается со строки, содержащей два целых числа N и P, количество учеников и количество учеников, которое нужно выбрать, соответственно. Затем следует еще одна строка, содержащая N целых чисел Si; i-й из них - это навык i-го студента.
Выходные данные
Для каждого тестового примера выведите одну строку, содержащую Case #x: y, где x - это номер тестового набора (начиная с 1), а y - минимальное количество часов, необходимых для тренировки, прежде чем вы сможете выбрать честную команду из учащихся P.
Limits
- Ограничение времени: 15 секунд на тестовый набор.
- Ограничение памяти: 1 ГБ.
- 1 ≤ T ≤ 100.
- 1 ≤ Si ≤ 10000, для всех i.
- 2 ≤ P ≤ N.
- Тестовый набор 1 (видимый)
- 2 ≤ N ≤ 1000.
- Тестовый набор 2 (скрытый)
- 2 ≤ N ≤ 105.
Образец
Вход
3
4 3
3 1 9 100
6 2
5 5 1 2 3 4
5 5
7 7 1 7 7
Выход
Case #1: 14
Case #2: 0
Case #3: 6
В примере № 1 вы можете потратить 6 часов на обучение первого ученика и 8 часов на обучение второго. Это дает первому, второму и третьему ученикам уровень квалификации 9. Это минимальное время, которое вы можете потратить, поэтому ответ - 14.
В примере №2 вы уже можете выбрать честную команду ( первый и второй ученик) без необходимости заниматься коучингом, поэтому ответ равен 0.
В примере № 3 P = N, поэтому каждый ученик будет в вашей команде. Вы должны потратить 6 часов на обучение третьего ученика, чтобы у него был навык 7, как и у всех остальных. Это минимальное время, которое вы можете потратить, поэтому ответ будет 6.
Мое решение основной пакет
import (
"bufio"
"fmt"
"os"
"strconv"
)
func main() {
scanner := bufio.NewScanner(os.Stdin)
scanner.Split(bufio.ScanWords)
scanner.Scan()
testcasesNumber, _ := strconv.Atoi(scanner.Text())
for i := 0; i < testcasesNumber; i++ {
var N []int
scanner.Scan()
n, _ := strconv.Atoi(scanner.Text())
scanner.Scan()
p, _ := strconv.Atoi(scanner.Text())
for j := 0; j < n; j++ {
scanner.Scan()
num, err := strconv.Atoi(scanner.Text())
if err != nil {
fmt.Println("Some random err")
}
N = append(N, num)
}
fmt.Printf("Case #%d: %d\n", i+1, solver(N, p))
}
}
func getMaxVal(arr []int) int {
res := arr[0]
for _, val := range arr {
if val > res {
res = val
}
}
return res
}
func solver(N []int, P int) int {
var added []int = make([]int, len(N))
newN := countSort(N)
added[0] = newN[0]
for idx := 1; idx < len(N); idx++ {
added[idx] = added[idx-1] + newN[idx]
}
minS := helper(newN, added, P, len(newN)-1)
for start := len(newN) - 2; start >= 0; start-- {
if start-P >= -1 {
curr := helper(newN, added, P, start)
if curr < minS && curr > 0 {
minS = curr
}
}
}
return minS
}
func helper(N []int, added []int, P, idx int) int {
res := P*N[idx] - added[idx]
if idx-P >= 0 {
res += added[idx-P]
}
return res
}
func countSort(N []int) []int {
k := getMaxVal(N)
count := make([]int, k+1)
for _, val := range N {
count[val]++
}
for i := 1; i < k+1; i++ {
count[i] = count[i] + count[i-1]
}
result := make([]int, len(N))
for j := 0; j < len(N); j++ {
result[count[N[j]]-1] = N[j]
count[N[j]] = count[N[j]] - 1
}
return result
}
Анализ
Сложность времени: O (n + k), k = постоянная
Сложность пространства: O (n)