Жадный алгоритм - минимизировать количество операций для выполнения задачи - PullRequest
Новая
       6

Жадный алгоритм - минимизировать количество операций для выполнения задачи

1 голос
/ 13 мая 2019

Я пытаюсь решить сложный вопрос программирования. Для удобства я подытожил это ниже:

Дан массив A целых положительных чисел. В одной операции мы можем выбрать один элементов в массиве A [i] и уменьшить его на фиксированную величину X. В то же время остальные элементы будут уменьшены на фиксированную сумма Y. Нам нужно найти минимальное количество операций, чтобы свести все элементы к неположительному числу (т. е. 0 и ниже).

Ограничения:
1 <= | A | <= 1e5 <br /> 1 <= A [i] <= 1e9 <br /> 1 <= Y <X <= 1e9 <br /> Ограничение времени: 1 секунда

Источник

Например, пусть X = 10, Y = 4 и A = {20, 20}.

Оптимальный подход для этого примера:

Операция 1: выберите пункт 0.

A = {10, 16}

Операция 2: Выберите пункт 0.

A = {0, 12}

Операция 3: Выберите пункт 1.

A = {-4, 2}

Операция 4: Выберите пункт 1.

A = {-8, -8}

Следовательно, ответ 4.

<Ч />

Мой подход:

Продолжайте выбирать максимальный текущий максимальный элемент в массиве и уменьшайте его на X (а остальные элементы уменьшайте на Y). Ясно, что этот подход превысил бы временные ограничения из-за, возможно, небольших значений X и Y (то есть число итераций, которые будет выполнять мой алгоритм, ограничено снизу max (A [i]) / 2).

Может кто-нибудь посоветовать мне лучшее решение?

1 Ответ

3 голосов
/ 13 мая 2019

Эту проблему можно решить с помощью бинарного поиска

Во-первых, мы хотим проверить, в пределах ли операций a, можем ли мы сделать все элементы равными <= 0;мы могли бы проверить для каждого элемента минимальное количество операций <code>b, так что если мы вычтем x для b операций и вычтем y для оставшихся a-b операций, то получим итоговое значение элементастанет <= 0. Суммируйте все эти числа вместе, и если <code>sum <= a, что означает, что мы могли бы использовать a операций.

Затем мы могли бы применить бинарный поиск для поиска действительного a. 

int st = 0;
int ed = max element / y + 1;
int result = ed;
while(start <= end){
    int mid = (st + ed)/2;
    int sum = 0;
    for(int i : A){
        sum += minTimesMinusX(i, mid);
    }
    if(sum <= mid){
        result = mid;
        ed = mid - 1;
    }else{
        st = mid + 1;
    }
}
return result;

Сложность времени O(n log max(A)).

...