У меня есть проблема:
Вам задан массив целых чисел A и целое число k. Вы можете уменьшить элементы массива A до k раз, чтобы создать последовательный подмассив, все элементы которого равны. Возвратите длину максимально возможного последовательного подмассива, который вы можете создать таким образом.
Например, если A равно [1,7,3,4,6,5], а k равно 6, вы можете получить [1,7,3,4 -1,6-1-1-1,5-1-1] = [1,7,3,3,3,3], поэтому вы вернете 4.
Какое оптимальное решение?
Подмассив должен быть сделан равным своему младшему элементу, поскольку единственной допустимой операцией является сокращение (а уменьшение самого нижнего элемента приведет к дополнительным затратам). Дано:
a1, a2, a3...an
стоимость снижения составляет:
sum(a1..an) - n * min(a1..an)
Например,
3, 4, 6, 5
sum = 18
min = 3
cost = 18 - 4 * 3 = 6
Один из способов уменьшить сложность с O(n^2) до логарифмического коэффициента: для каждого элемента как самого правого (или самого левого) элемента подмассива-кандидата наилучший двоичный поиск наибольшей длины в пределах стоимости. Для этого нам нужна только сумма, которую мы можем получить из суммы префиксов за O(1), длина (по которой мы уже ищем) и запрос минимального диапазона, который хорошо изучен.
В ответ на комментарии под этим постом, вот демонстрация того, что последовательность затрат, когда мы расширяем подмассив от каждого элемента до крайнего правого, монотонно увеличивается и, следовательно, может быть запрошена с помощью двоичного поиска.
Код JavaScript:
function cost(A, i, j){
const n = j - i + 1;
let sum = 0;
let min = Infinity;
for (let k=i; k<=j; k++){
sum += A[k];
min = Math.min(min, A[k]);
}
return sum - n * min;
}
function f(A){
for (let j=0; j<A.length; j++){
const rightmost = A[j];
const sequence = [];
for (let i=j; i>=0; i--)
sequence.push(cost(A, i, j));
console.log(rightmost + ': ' + sequence);
}
}
var A = [1,7,3,1,4,6,5,100,1,4,6,5,3];
f(A);min, используя запрос минимального диапазона. Используя это min, мы вычисляем максимальную длину, возможную при заданной стоимости. Кроме того, нам нужно иметь массив сумм префиксов для части sum(a1..an). Поправьте меня, если ошибаюсь.
- person Shridhar R Kulkarni; 20.12.2020
def cost(a, i, j):
n = j - i
s = 0
m = a[i]
for k in range(i,j):
s += a[k]
m = min(m, a[k])
return s - n * m;
def solve(n,k,a):
m=1
for i in range(n):
for j in range(i,n+1):
if cost(a,i,j)<=k:
x = j - i
if x>m:
m=x
return m
Это мое решение python3 в соответствии с вашими спецификациями.
