Какой алгоритм использовать, чтобы: разбить массив чисел так, чтобы суммарная разница между максимальным и минимальным числом была максимальна?
У меня есть массив чисел, мне нужно разбить его на группы так, чтобы каждая из них была длины от l до r (менять порядок чисел (сортировать) нельзя) и, чтобы суммарная разница между максимальным и минимальным числом была максимальна.
Если разбиение возможно несколькими способами, то вывести любой из них
Например, есть массив [98, 99, 98, 100, 98, 99, 98]; l = 2; r = 4. В ответе будет разбиение на 3 подмассива: [98, 99] [98, 100] [98, 99, 98]. Суммарная разница здесь будет 4.
Я вот думаю, есть ли тут динамическое программирование?
Ага, ДП тут отлично входит. F(n) - ответ на задачу для префикса длины n. Там перебираете длину последней группы x и берете в качесвте ответа max(a[n-x]..a[n-1]) - min(a[n-x]..a[n-1]) + F(n-x). По всем l<=x<=r выбераете максимум. Если n < l, то ответ - минус бесконечность.
Это будет решение за O(n^2). Что-нибудь за O(n log n) я так сходу придумать не могу.
базово на каждую новую n придется сделать O(r-l) итераций для поиска максимумов и минимумов
итого O(n * (r - l)), там может (r - l) сильно меньше n.
но если они таки сравнимы с n, то ещё навскидку кажется (хотя и нельзя сказать наверняка), что для вычисления max и min в очередной группе можно применить тот прием со стеком, который используется для вычисления оных на sliding window. Последняя группа смещается похожим образом. Если так, то будет вообще линейно.
Может. Но пока об этом ничего не сказано, оценка сверху остается O(n) на каждое f().
что для вычисления max и min в очередной группе можно применить тот прием со стеком, который используется для вычисления оных на sliding window. Последняя группа смещается похожим образом. Если так, то будет вообще линейно.
Ну не, это же только для фиксированного размера группы сработает. Если там хоть какой-то разброс есть r-l, то sliding window уже нe работает.
BAF1, Попробуйте тест aaaaa 3 4
Должно быть NO SOLUTION.
А можно ли вывести всю строку, как одно слово? Вы, вроде как требуете всегда хотя бы 2 слова, но, может это и не надо? В тесте aaaaa 5 5 должно вывести одно слово aaaaa.
Wataru, уже прошёл тот тест с помощью строчки sequence.length != result.first.joinToString("").length, но теперь не проходит по времени (ограничение 1 секунда, а у меня 1.087), если нужен код вот, тот удалил:
fun main() {
Task5().run()
}
class Task5 {
fun run() {
val (_, l, r) = readln().split(" ").map { it.toInt() }
val sequence = readln()
val result = maxDifference(sequence, l, r)
if (sequence.length != result.first.joinToString("").length) {
println("NO SOLUTION")
return
}
println(result.second)
println(result.first.size)
println(result.first.joinToString("\n"))
}
private fun maxDifference(a: String, l: Int, r: Int): Pair<List<String>, Int> {
val n = a.length
val words = Array(n + 1) { Pair(emptyList<String>(), 0) }
for (i in l..n) {
for (x in l..r) {
if (i >= x) {
val slice = a.substring(i - x, i)
var maxChar = Int.MIN_VALUE
var minChar = Int.MAX_VALUE
for (char in slice) {
val code = char.code
if (code > maxChar) maxChar = code
if (code < minChar) minChar = code
}
val new = words[i - x].second + (maxChar - minChar)
if (words[i].second <= new) {
val newArr = words[i - x].first.toMutableList()
newArr.add(slice)
words[i] = Pair(newArr, new)
}
}
}
}
return words.last()
}
}
Простой
