Уменьшение времени выполнения программы
Здравствуйте! Решение задачи превышает превышает положенное время (ограничение времени 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()); } } } }
Как уменьшить время выполнения программы?
Помогите пожалуйста сократить время выполнения программы. Работает за 5.008 сек, а должна за 1 сек. Вот код:
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 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85
#include #include using namespace std; #define max 100000 // (максимальный возможный путь состоит 99 переходов по 1000) int n; // Число вершин графа int m; // Число запросов int A; // Стартовая вершина int dlina[101]; // Длины путей до всех вершин графа int a[101][101]; // Матрица смежности графа std::vectorint> paths[101]; // Пути до всех вершин графа void new_dlina(int k) { for (int i = 1; i n; i++) { if (k != i && a[k][i] != -1) { if (dlina[i] > dlina[k] + a[k][i]) { dlina[i] = dlina[k] + a[k][i]; paths[i] = paths[k]; paths[i].push_back(i); new_dlina(i); } } } } // Главная функция int main() { //freopen("INPUT.TXT", "r", stdin); //freopen("OUTPUT.TXT", "w", stdout); scanf("%d%d%d", &n, &m, &A); // ввод исходных данных for (int i = 1; i n; i++) { dlina[i] = max; // присвоение максимального значения } dlina[A] = 0; paths[A].push_back(A); // получаем матрицу смежности for (int i = 1; i n; i++) { for (int j = 1; j n; j++) { scanf("%d", &a[i][j]); } } new_dlina(A); // Получаем список вершин и распечатываем пути for (int i = 1; i m; i++) { int w; scanf("%d", &w); if (dlina[w] == max ) /* сравнение с максимальным */ { printf("No path"); // вывод, что пути - нет ! } else { printf("%d %d ", dlina[w], paths[w].size()); for (int j = 0; j paths[w].size(); j++) { printf("%d ", paths[w][j]); } printf("\n"); } } return 0; }
94731 / 64177 / 26122
Регистрация: 12.04.2006
Сообщений: 116,782
Ответы с готовыми решениями:
Как вы тестируете время выполнения программы?
Добрый день. Вопрос к олимпиадникам: как вы тестируете время выполнения ваших программ во время.
Как зафиксировать время начала выполнения программы
Здравствуйте) подскажите, пожалуйста, как зафиксировать время начала выполнения программы и.
Как уменьшить время работы программы? C++
Как уменьшить время работы программы?
Выведите на первой строке число от 1 до n, включительно, которое имеет максимальное число делителей. На второй строке выведите число его делителей. Если есть несколько чисел от 1 до n с максимальным числом делителей, выведите любое из них.
Я для трех чисел написал исключение, но замечу что и без него все равно превышено ограничение по времени, n меньше либо равно 100000 (10^5).
Беда именно с большими числами.
#include
using namespace std;
Лучший ответ
твой алгоритм имеет квадратичное время работы, т. к. поиск числа делителей выполняется за линейное время
тривиальный алгоритм поиска делителей n может перебирать числа только до sqrt(n), а не до n/2, тогда любой делитель d в диапазоне [1; sqrt(n)] будет иметь парный делитель n / d, и мы будем добавлять к ответу сразу 2, а не 1 (кроме случая, когда n = d^2)
и да, вынеси поиск числа делителей в отдельную функцию
Илья МуромецУченик (141) 2 года назад
Здравствуйте, спасибо за ответ, можете пожалуйста исправить нужную строчку (и) в коде, я суть понял, но почему-то программа начала выдавать половину правильных ответов, буду очень благодарен!
user49913 Просветленный (37133) int DivisorsCount(int n) < int ret = 0; for (int d = 1; d * d > > return ret; > присобачишь как-нибудь
Остальные ответы
циклиться до sqrt(n), а не до n/2
если i является делителем, то n/i тоже делитель
<от 1 до n, включительно, >
вот определите это число как
int maxNumber = 12345. ;
и сначала тестируйте алгоритм на нем (без ввода cin >> maxNumber;)
и ищите от большего к меньшему
for ( int i = maxNumber; i > 1; i—)
возможно не нужно перебирать все числа (решение в лоб),
а использовать признаки делимости чисел.
Ответы режут форматирование, поэтому свой код лучше
копировать сюда https://pastebin.com
в Ответы давать только ссылку на код.
Избегайте лишних фигурных скобок, это только ухудшает понимание.
if (i % j == 0)
k++;
>
Здесь один оператор всего, лучше записать так:
if (i % j == 0) k++; // одна строчка вместо четырех
// не забывайте хотя бы делать краткие комментарии к коду,
// тем более когда его будут читать другие программисты
λИскусственный Интеллект (206085) 2 года назад
в ссылке готовый код. не тестировал, не вникал.
https://pastebin.com/K5iQdQAA
user49913Просветленный (37133) 2 года назад
совет про фигурные скобки весьма спорный
это сейчас там один оператор, а если понадобится второй добавить?
придётся доставлять ручками фигурные скобки, а ещё можно (с похмелья, например) вообще забыть их добавить и потом искать багу много минут
да и диффы куда красивее получаются
обычная практика в индустрии — это как раз всегда ставить фигурные скобки, даже если оператор один
пример — google c++ style guide
λ Искусственный Интеллект (206085) user49913, Стиль — дело вкуса. ( Пишу (я на лиспе) вообще (без скобок ни как))
Как уменьшить время выполнения программы, написанной на С++?
Задача: Какое наименьшее число 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; >- Вопрос задан более трёх лет назад
- 2356 просмотров
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
ты вместо букв подставляешь первые несколько простых чисел — и смотришь какой вариант даст минимальное число.
Чем больше раз буква встречается — тем меньшее простое число должно ей соответствовать.
Но всё равно может быть придётся проверить несколько вариантов.