Форум программистов, компьютерный форум, киберфорум
Наши страницы

Оптимизация времени выполнения - C++

Войти
Регистрация
Восстановить пароль
Другие темы раздела
C++ Пpи помощи стека пpовести соpтиpовку http://www.cyberforum.ru/cpp-beginners/thread594746.html
Дан файл, элементами котоpого являются целые числа, упоpядоченные по возpастанию (убыванию). Пpи помощи стpуктуpы данных стек пpовести "обpатную" соpтиpовку файла по убыванию (возpастанию!)
C++ Вывести числа в порядке убывания, вычислить площадь треугольника Проверить задачу если возможно - собственно прошу вас посмотреть эту задачу. Условие: Ввести три числа. Если они могут быть длинами сторон тупоугольного треугольника, вывести их в порядке... http://www.cyberforum.ru/cpp-beginners/thread594743.html
Как записать ответ с методом пузырька? C++
Собственно програмка выдает около 100 разных значений, как можно было бы записать их методом пузырька в массив? Или еще лучше, если бы, например у нас есть ответ, 2 параметра результата, например...
Преобразование символов в числа C++
Дан текст, содержащий цифры. Вывести на экран наибольшую цифру. Помогите пожалуйста))
C++ База данных студентов (найти ошибки) http://www.cyberforum.ru/cpp-beginners/thread594688.html
доброго всем время суток!!!!хотел бы обратится за помощью к тем,кто с программированием на "ты". просьба небольшая,просто я написал прогу на С++ и хотел бы,чтобы проверили код проги на ошибки. если...
C++ Написать программу, которая вычисляет среднее арифметическое последовательности дробных чисел программа с++ помогите с программой, выдает ошибку и закрывается после ввода количества чисел Написать программу, которая вычисляет среднее арифметическое последовательности дробных чисел,... подробнее

Показать сообщение отдельно
valeriikozlov
Эксперт С++
4673 / 2499 / 321
Регистрация: 18.08.2009
Сообщений: 4,550
03.06.2012, 21:35
Цитата Сообщение от CLEO_ROCK Посмотреть сообщение
Мой код на сервере работает 1,014 с.
это не значит, что не хватает всего 0,014 с, вполне возможно что тестирующая система просто прерывает дальнейшую проверку при превышении времени выполнения уже на 0,014 с (я с таким сталкивался).
Nick Alte предложил хороший способ, но этим время сильно не выиграешь. Основная причина TL кроется здесь:
Цитата Сообщение от CLEO_ROCK Посмотреть сообщение
k (k ≤ 100 000)
Цитата Сообщение от CLEO_ROCK Посмотреть сообщение
Если xi > 0, то .... При этом 1 ≤ xi ≤ yi ≤ 100 000.
Т.е. может быть тест(ы), когда нужно около 100 000*100 000 итераций. Ни в какую секунду не влезет.
Предлагаю такой вариант:
завести еще один массив для хранения элементов типа структур. Каждый элемент такого массива будет хранить данные о диапазоне размером 1000 элементов. Т.е. элемент [0] такого массива будет хранить данные об элементах массива a[1]..a[1000]. Элемент [1] такого массива будет хранить данные об элементах массива a[1001]..a[2000]. И т.д. А хранить в каждом элементе такого массива нужно только минимальное и максимальное значение масива a[] в этом диапазоне.
Заполнение такого массива можно сделать на этапе заполнения массива a[].
Когда xi < 0, то нужно не только заменить значение в a[] но и посмотреть, не нужно ли менять значение min max в новом массиве для соответствующего диапазона.
Когда xi > 0, то искать максимальный и минимальный элемент нужно в новом массиве, и в a[] - в оставшихся кусочках, которые полностью не покрыты новым массивом.
Например xi=255, yi=6031:
- сначало минимальный и максимальный элемент ищем в новом массиве с [1] по [6] а потом ищем в массиве a[] с a[255] по a[1000] и с a[6001] по a[6031].
1
 
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2017, vBulletin Solutions, Inc.
Рейтинг@Mail.ru