Как уменьшить время выполнения программы c

Уменьшение времени выполнения программы

Здравствуйте! Решение задачи превышает превышает положенное время (ограничение времени 1 секунда). Подскажите, пожалуйста, как можно сократить время выполнения программы?

Формат ввода
Первая строка входного файла — целое число N от 0 до 105 — общее количество оценок.
Далее идут N строк, каждая из которых содержит фамилию очередного студента (строка из латинских букв длиной от 1 до 20 символов) и его оценку — целое число от 0 до 109.

Формат вывода
Выведите N строк. k-я строка должна содержать среднюю оценку студента, которому была выставлена k-я оценка в исходном списке, после объявления k оценок. Средняя оценка округляется до ближайшего целого вниз (то есть, от нее отбрасывается дробная часть).

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39

#include #include #include using namespace std; int main() { mapstring, vectorint>> list; vectorstring> names; int n; cin >> n; for (int i = 0; i  n; ++i) { string name; int mark; cin >> name >> mark; list[name].push_back(mark); names.push_back(name); } for (auto & i : list) { vectorint> v; int sum = 0; int i_size = i.second.size(); for (int j = 0; j  i_size; ++j) { sum += i.second[j]; int res = sum / (j + 1); v.push_back(res); } i.second = v; } for (auto & name : names) { int i = 0; for (auto & it : list) { if (name == it.first) { cout  second[0]; if (i != n - 1) cout  <"\n"; ++i; it.second.erase(it.second.begin()); } } } }

Как уменьшить время выполнения программы?

Переписать алгоритм. А чтобы в этом вам помочь, для начала хотелось бы понять что делает данный алгоритм. На первый взгляд, это поиск числа от 1 до n, сумма делителей которого максимальная, верно?

Ответ написан более трёх лет назад
yll3 @yll3 Автор вопроса

Нет смысла во втором цикле бежать до n. Как минимум можно бежать только до i, а ещё лучше до sqrt(i). И делать не S=S+j;, а S=S+j+i/j;
Это уже значительно ускорит работу программы. А если понять что корень возрастает медленно и не считать его для каждого i, а увеличивать на единицу переменную в которой хранится корень, то.

Ответ написан более трёх лет назад
Комментировать
Нравится Комментировать
Ответы на вопрос 1
JoyceGraham @JoyceGraham

На первый взгляд почему бы не вынести
if(S > Smax)
за пределы второго цикла? А то получается при каждом проходе идет проверка.

Ответ написан более трёх лет назад
Комментировать
Нравится Комментировать
Ваш ответ на вопрос

Войдите, чтобы написать ответ

• Linux
• +1 ещё

Как сделать многопоток сокетов?

• 1 подписчик
• 5 часов назад
• 57 просмотров

Как уменьшить время выполнения программы, написанной на С++?

Задача: Какое наименьшее число n можно представить в виде произведения n = a∙b ровно k способами? Произведения a∙b и b∙a считаются одним способом, все числа натуральные (1 ≤ k ≤ 50).
Лимит времени: 1 сек.
При k=50 у меня тратится больше 2 сек.
Программный код:

int factors(int); int main() < int k; cin>>k; cout int factors(int k) < int n=0, kol; while(true) < kol=0; n++; for (int i=n; i>0; i--) if (n%i==0) < if (i*i==n) kol=kol+2; else kol++; >if (kol/2==k) break; > return n; >

• Вопрос задан более трёх лет назад
• 2423 просмотра

3 комментария

Оценить 3 комментария

Какое жуткое форматирование. Ctrl+k, d в студии сделайте.

Не до конца понятна суть задачи. Например, нужно найти 50 способов (если k=50) представить число 153 (n=153) в виде произведения двух чисел (a*b), правильно я понял? Можно увидеть конкретный результат для какого-нибудь числа?

yuharu @yuharu Автор вопроса

Антон Федорян: например введено число k=3, то есть нужно найти наименьшее число, которое можно составить из 3 произведений чисел, ответом будет 12, т.к. 1*12, 2*6, 3*4

Решения вопроса 0
Ответы на вопрос 2
whiteBlackness @whiteBlackness

Самый лучший способ — это алгоритм поменять. У тебя тут тупой перебор.
Гораздо эффективнее зайти с другой стороны задачи.
Любое число факторизуется на произведение простых чисел.
Тебе просто надо понять на сколько простых чисел должно факторизоваться твоё число — и взять столько первых простых чисел.

1 пара у тебя всегда есть. 1 * само число.
Осталось понять какая должна быть струтура факторизации числа (сколько должно быть одинаковых простых чисел и сколько различных).

Ответ написан более трёх лет назад
Нравится 3 3 комментария
yuharu @yuharu Автор вопроса

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

whiteBlackness @whiteBlackness

yuharu: так я и написал как. Не перебирать все числа, а сначала понять, какое должно быть разложение на простые числа (факторизация). А потом просто взять первые несколько простых чисел — тогда будет минимальное число.

Твоё искомое число представляется в a * a * . * a * b * b * .. * b * c ..
где a, b, c — это различные простые числа.
Например
2 * 2 * 3 * 5 * 5

Данное разложение можно разделить пополам несколькими различными способами
| aabcc
a | aabcc
aa | bcc
ab | abcc
.
и т.д.

Число таких вариантов разделения — это твоё k

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

После этого, как у тебя появилось несколько претендентов на разделение
например aabbc и abcd
ты вместо букв подставляешь первые несколько простых чисел — и смотришь какой вариант даст минимальное число.

Чем больше раз буква встречается — тем меньшее простое число должно ей соответствовать.
Но всё равно может быть придётся проверить несколько вариантов.

Как уменьшить время выполнения с 1 секунды хотябы до 100 мс в легчайшем алгоритме?

Решил написать простую программу в целях обучения и практики. Решение правильное, но очень медленное. Сдаю задачку на сайте, 13 из 27 тестов выдаёт около 2 секунд, а нужно меньше 1 секунды. Постарался максимально сократить все if-ы, которые только возможно было, но и это не помогает. Думаю, что основное время затрачивается на прокрутку цикла, но иначе задачу не решить же. У других пользователей среднее время в этой задачке от 14 до 100 мс. Я просто недавно начал, и может этот алгоритм который я написал совсем никак не ускорить, но по другому я просто не представляю как можно это решить. условие задачи Новый русский Витек приватизировал участок в Междолине размером m квадратов с севера на юг и n квадратов с запада на восток. Он решил построить в пределах этого участка дом размером a квадратов с севера на юг и b – с запада на восток. Некоторые квадраты радиоактивны, и Витек не хочет на них строить дом. Кроме того, Витек хочет, чтобы расстояния от стен до границ участка выражалась целым числом квадратов. Долго выбирал он место для дома, но так и не выбрал – слишком много вариантов. А сколько? Начал наш герой считать, но не сумел – плохо математику учил. Помогите ему. Входные данные Напишите программу, которая считывает числа m, n, a, b, k (1 ≤ a ≤ m ≤ 5000, 1 ≤ b ≤ n ≤ 5000, 0 ≤ k ≤ m * n), где m, n – размеры участка, a и b – размеры дома, k – количество радиоактивных квадратов, а затем k неповторяющихся пар чисел i и j (1 ≤ i ≤ m, 1 ≤ j ≤ n), которые определяют координаты радиоактивных квадратов. Выходные данные Вывести искомое количество способов расположения дома. На С++

#include using namespace std; int main() < int m, n, a, b, k, S, Ox, Oy, Oxmain = 1, Oymain = 1, l, t; // m висота n ширина; a висота b ширина bool y = false; cin >> m >> n >> a >> b >> k; int i[100000]; for (l = 1; l > i[l] >> i[l + 1]; > S = a * b; l = 0; while (Oymain > > Oy = Oymain; > if (y); else l++; y = false; Oxmain++; > Oxmain = 1; Oymain++; > cout

Отслеживать

задан 9 окт 2020 в 19:39

user410415 user410415

У вас матрешка из 5-ти вложенных циклов, хотя вложенность 2-й степени циклов уже дает O(n^2) .

9 окт 2020 в 19:55

Матрица m * n заполнена нулями, к точкам с данными индексами, присваиваются единицы. Теперь нужно считать количество площадей, размером a * b, где не встречаются элементы с ненулевым значением