Максимизировать распределяемую премию

Question

Петр Васильевич, директор ОАО "Рога и рога", собирается раздать премию всем менеджерам компании, он добрый и честный человек, поэтому хочет соблюсти следующие условия:

премия должна быть равной для всех менеджеров должна быть максимально возможной и целой должна быть выдана одной транзакцией с одного счета для каждого менеджера, без использования нескольких счетов для отправки одной премии

У Петра Васильевича открыто N корпоративных счетов, на которых лежат разные суммы денег Cn, а в компании работает M менеджеров. Необходимо выяснить максимальный размер премии, которую можно отправить с учетом условий. Если денег на счетах компании не хватит на то, чтобы выдать премию хотя бы по 1 у.е. - значит премии не будет, и нужно вывести 0.

Входные данные (поступают в стандартный поток ввода) Первая строка - целые числа N и M через пробел (1≤N≤100 000, 1≤M≤100 000)

Далее N строк, на каждой из которых одно целое число Cn (0≤Cn≤100 000 000)

Проверка входных данных и обработка неправильных данных на входе не нужна, тестовые данные для проверки гарантированно подходят под описание выше

Выходные данные (ожидаются в стандартном потоке вывода) Одно целое число, максимально возможная премия

Пример 1 Ввод:

Вывод:

Пример 2 Ввод:

2 100
99
1

Вывод:

Пример 3 Ввод:

2 100
98
1

Вывод:

Мой алгоритм сортировки

Arrays.sort(cn);
int left = cn[0];
int right = cn[cn.length - 1];
int mid = 0;
while (right - left > 1) {
    sum = 0L;
    mid = (right + left) / 2;
    for (int i = 0; i < n; i++) {
    sum += cn[i] / mid;
    }
if (sum < m) {
    right = mid;
} else {
    left = mid;    
}
        System.out.println(left);

Answer 1

Есть очевидное решение с бинпоиском. Перебираем размер премии и проходом по массиву определяем, скольки людям смогли её выдать. Асимптотика O(n*lb(max)).

PS: Думаю, что существует линейное решение, но я его не придумал, а это почти наверняка достаточно хорошее.

Answer 2

Вариант с последовательным перебором от среднего арифметического (максимально возможного) по нисходящей до первого допустимого:

function largestBonus(N,M,...Cn){
    const accounts = [...Cn];
    const max = Math.floor(accounts.reduce((sum,item) => sum + item, 0)/M);
    for(let b = max; b > 0; b--){
        if(accounts.reduce((sum,item) => sum + Math.floor(item/b), 0) >= M){
            return b;
        }
    }
    return 0;
}

console.log(largestBonus(4,6,199,453,220,601));
console.log(largestBonus(2,100,99,1));
console.log(largestBonus(2,100,98,1));

Вариант с двоичным поиском наибольшего из диапазона от 0 до среднего арифметического:

function largestBonus(N,M,...Cn){
    const accounts = [...Cn];
    let max = Math.floor(accounts.reduce((sum,item) => sum + item,0)/M);
    let min = 0;
    let cur = 0;
    while(max != min){
        cur = Math.ceil((max + min)/2);
        if(accounts.reduce((all,account) => all + Math.floor(account/cur),0) >= M){
            min = cur;
        } else {
            max = cur - 1;
        }
    }
    return cur;
}

console.log(largestBonus(4,6,199,453,220,601));
console.log(largestBonus(2,100,99,1));
console.log(largestBonus(2,100,98,1));

Answer 3

Решил вот так, но почему то проверку не проходит по второму тесту. Хотя в IDE все окей. Подскажите, если кто что заметит.

    function amountOfReward(n, m, accounts) {

    let topLimit = Math.floor(accounts.reduce((sum, item) => sum + item, 0)/m);

    if (topLimit < 1) {
        return 0;
    } else if (topLimit === 1) {
        return 1;
    } else {
        let bottomLimit = 1;
        let counter = 0;
        let swap = 0;

        while (true) {

            for (let i = 0; i < accounts.length; i++) {
                if (accounts[i] / topLimit >= 1) {
                    counter += Math.floor((accounts[i] / topLimit));
                }
            }

            if (counter < m) {
                topLimit = Math.floor(topLimit - (topLimit - bottomLimit) / 2);
                swap = topLimit;
                counter = 0;
            } else if (counter > m) {
                bottomLimit = swap;
                topLimit = Math.floor(topLimit + topLimit / 2);
                counter = 0;
            } else {
                return topLimit;
            }
        }
    }
}

console.log(amountOfReward(4, 6, [199, 453, 220, 601]));
console.log(amountOfReward(2, 100, [99, 1]));
console.log(amountOfReward(5, 6, [1, 1, 1, 1, 1]));
console.log(amountOfReward(3, 5, [25, 37, 3]));
console.log(amountOfReward(4, 27, [199, 453, 220, 601]));
console.log(amountOfReward(1, 2, [1]));

БЛОГ НА HUSL

Максимизировать распределяемую премию

Ответы (3 шт):