Как оптимизировать данный код?

Question

[student_1]

как можно оптимизовать данный код?\
требование:
Ограничение времени, с 1
Ограничение памяти, МБ 64

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

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

4 6
199
453
220
601
Вывод:

200

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

2 100
99
1
Вывод:

1

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

2 100
98
1
Вывод:
0
проблема: Код работает, но не проходит по пункту: Превышение лимита памяти
код:

import java.util.Scanner;

class Main {
    public static void main(String[] args) {
        int pays = 0;
        try {
            Scanner scan = new Scanner(System.in);
            String str = scan.nextLine();
            int n = Integer.parseInt(str.split(" ")[0]);
            int m = Integer.parseInt(str.split(" ")[1]);
            int[] acc = new int[n];
            int summa = 0;
            for (int i = 0; i < acc.length; i++) {
                acc[i] = Integer.parseInt(scan.nextLine());
                summa += acc[i];
            }

            if(summa > 0 && m > 0) pays = summa/m;
            if(pays != 0) {
                while(true) {  // здесь занимает больше всего ресурсов 
                    int g = 0;
                    for (int i = 0; i < acc.length; i++) {
                        g += acc[i] / pays;
                    }
                    if(g >= m) break;
                    else pays--;
                }
            }
        } catch (Exception ex) {}
        finally {
            System.out.println(pays);
        }
    }
}

Comments

[Daria Motorina]

While(true) это сам по себе бесконечный цикл, он тут не нужен, for внутри него уже решает задачу

[Алексей Черемисин]

Да я бы сказал, что здесь и первым for можго вполне обойтись! Что два раза скакать по одному и тому же бегать.. Даже не два раза, а какое-то непонятное количество - без прерывания while

Answer 1

[Odissey Nemo]

1. Памяти под внутренние переменные в приведённых примерах практически не выделяется. вообще
Если требование по памяти относится именно к памяти под данные, то условие однозначно выполнено!
А вот требование по памяти всего процесса, под систему, код и данные, и если 50 мегабайт не хватило, то проблема явно не в данных, а настройках компилятора. Например. можно уменьшить размер стека из хипа, который тут практически не требуется.
2. Как проверяется условие по памяти? У меня на версии Java 8 следующий код сообщает, что занято 20 мегабайт:

Runtime rt = Runtime.getRuntime();
        long usedMB = (rt.totalMemory() - rt.freeMemory()) / 1024 / 1024;
        System.out.printf("Usage mamory %d Mb%n", usedMB);

3. Возможно, для уменьшения потребности в памяти следует взять менее прожорливую версию Java. Уверен, что от версии к версии требования к памяти чисто под системные модули однозначно растёт в большую сторону. Хотя с т.з. Java вообще затруднительно отделить память рантайма и кода с данными пользователя. Т.е. 50 мегабайт - это может быть размер программы типа "Hellо World" для Java 8+.

Answer 2

[Василий Банников]

1. try-catch - это дорого, и вообще предназначен он для исключительных ситуаций.
2. Тут можно только 1 раз вызвать str.split

int n = Integer.parseInt(str.split(" ")[0]);
            int m = Integer.parseInt(str.split(" ")[1]);

3. Здесь нет динамического выделения памяти, так что врядли

while(true) {  // здесь занимает больше всего ресурсов 
                    int g = 0;
                    for (int i = 0; i < acc.length; i++) {
                        g += acc[i] / pays;
                    }
                    if(g >= m) break;
                    else pays--;
                }

Тк нужно оптимизировать выделение памяти - советую посмотреть на диапазон значений, и использовать в массиве наиболее маленький тип данных.

Answer 3

[rPman]

if(g >= m) break;
else pays--;

из-за этих двух странных строк (логику понять не могу, если текущая взвешенная сумма станет больше указанного на старте значения то прекращяем, иначе вычитаем 1 из pays которая поделенная сумма на m, логику чисел pays и m я понять не могу) избавиться от acc не получится, (в твоем коде нет ничего жрущего оперативную память кроме этого массива) так как нужно сначала посчитать всеобщую сумму. Т.е. если приложению на вход дать 16 миллионов строк (или 8 миллионов, int там 8 или 4 байтный?) то приложение точно выйдет за лимит памяти.

Comments

[Василий Банников]

Это жава, так что int всегда 4 байта