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

С++ для начинающих

Войти
Регистрация
Восстановить пароль
 
ZaMaZaN4iK
Мой лучший друг-отладчик!
164 / 164 / 9
Регистрация: 24.06.2012
Сообщений: 662
Записей в блоге: 5
Завершенные тесты: 1
#1

Интересная задачка(оптимизация) - C++

20.11.2012, 16:26. Просмотров 394. Ответов 5
Метки нет (Все метки)

Вот недавно писал районку по информатике.И там была такая вот задача.Я то её решил, но у меня даже ввод чисел из некоторых тестов не проходит.Прошу вас, как более опытных программистов, помочь мне её оптимизировать.
Вот условие задачи:
Задача E. Конфеты
Ограничение по времени: 2 секунды
Ограничение по памяти: 256 мегабайт Ввод: с клавиатуры
Вывод: на экран
Как известно всем, Питер очень любит сладкое.
Сегодня он купил N упаковок конфет по ai штук в каждой и приступил к их поеданию. Только в этот раз Питер ест их необычным способом.
Он выбирает определённое число m и съедает из каждой коробки (ai –m) конфет. Например, у Питера есть 5 коробок с 3, 2, 8, 9 конфетами. Пит выбрал число 4. Тогда из первой и второй коробки он ничего не съест (в них конфет меньше, чем 4), а из двух последних коробок он съест 4 и 5 конфет. Таким образом, получим, что в пяти коробках будет лежать 3, 2, 4, 4 конфет соответственно.
Питер хочет выбрать такое наибольшее число m, чтобы съесть как минимум K конфет.

Формат ввода:
В первой строке ввода находятся целые числа N и K (1 ≤ N ≤ 10 в 6 степени, 1 ≤ K ≤ 2*(10 в 9 степени)).
В следующей строке записано N целых чисел через пробел: количество конфет в каждой коробке, которое не превышает 10 в 9 степени.

Формат вывода:
Выведите одно число – ответ на задачу.


вот мои наработки, код рабочий, но не очень быстрый:
C++
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
#include <iostream>
 
using namespace std;
 
int main()
{
    long long n,k,max=-1,count=0;
    сin>>n>>k;
    long long *mas=new long long[n];
    for(long long i=0;i<n;i++)
    {
    сin>>mas[i];
    if(mas[i]>max)
    max=mas[i];
    }
    while(max)
    {
       for(long long i=0;i<n;i++)
       {
       if(max<mas[i])
          count+=mas[i] - max;
       if(count>=k)
       goto v1;
       }
       count=0;
       max--;
    }
    v1:
    сout<<max;
    return 0;
}
0
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
20.11.2012, 16:26
Здравствуйте! Я подобрал для вас темы с ответами на вопрос Интересная задачка(оптимизация) (C++):

Интересная задачка - C++
#include &lt;iostream&gt; #include &lt;math.h&gt; using namespace std; int main() { double z1,z2; double a,b,c,d,s,t,u; ...

Очень интересная задачка на C++ - C++
Исследовать сходимость ряда Фурье по косинусам для функции f(x)=l-x на отрезке ,l=1. Определить, сколько членов ряда Фурье необходимо...

Одна интересная задачка - C++
Помогите, пожалуйста, с написанием программы. Буду благодарна, если даже просто подтолкнете к мысли решения. Даны натуральное число...

Интересная задачка, метод кв. корней - C++
Здрасте вам. Сейчас пытаюсь реализовать метод квадратных корней в С++. Вот что у меня пока-что получилось: #include &lt;cstdlib&gt; #include...

Интересная задачка, и блок схема нужна С++ - C++
Плот составлен из n бревен длиной l и диаметром d. Со-ставить программу определения, выдержит ли этот плот k пу-тешественников со средней...

Знатоки С++ и СИ, где вы ? Интересная олиппиадная задачка (Нужно перевести ) - C++
Буду благодарна за любую помощь // Меньшиков. Тренировка 1. // 1E. Степень // Длинная арифметика // ibelyaev: 20Feb2010 ...

Надоела реклама? Зарегистрируйтесь и она исчезнет полностью.
valeriikozlov
Эксперт C++
4670 / 2496 / 321
Регистрация: 18.08.2009
Сообщений: 4,550
20.11.2012, 17:29 #2
Если max уменьшать на 1, то будет очень долго. Здесь нужен двоичный поиск. Изначально левая граница l=0, правая граница r=max. Нужно найти такое x, при котором count>=k и при (x+1) count<k.
Выбираете x=(l+r)/2. Проверяете что получится при x и при x+1 (это делаете в одном цикле). Если оба значения меньше k, то делаете r=x. Если оба значения count>k, то l=x.
1
ZaMaZaN4iK
Мой лучший друг-отладчик!
164 / 164 / 9
Регистрация: 24.06.2012
Сообщений: 662
Записей в блоге: 5
Завершенные тесты: 1
20.11.2012, 19:17  [ТС] #3
valeriikozlov, ваш способ очень интересен, сейчас его попробую.Но вот проблема в чём есть ещё - у меня по времени не проходит даже считывание знчений с файла!У меня лимит 2 секунды, а считывание файла со значениями( файл весит 5.5 мб - предсталяете я думаю, сколько там чисел.И их кол-во к сожалению влазаят в ограничение) занимает примерно 6 секунд.Что с этим делать?
0
LineStown
66 / 66 / 3
Регистрация: 04.08.2010
Сообщений: 420
Завершенные тесты: 1
20.11.2012, 19:23 #4
Цитата Сообщение от ZaMaZaN4iK Посмотреть сообщение
Ограничение по памяти: 256 мегабайт Ввод: с клавиатуры
В условии как бы ввод с клавиатуры) Соответственно 2 секунды на расчет, а не на считывание из файла.)
1
diagon
Higher
1929 / 1195 / 49
Регистрация: 02.05.2010
Сообщений: 2,925
Записей в блоге: 2
20.11.2012, 19:58 #5
Используйте scanf/printf вместо cin/cout.
Если совсем плохо, то fread с ручным парсингом.
0
ZaMaZaN4iK
Мой лучший друг-отладчик!
164 / 164 / 9
Регистрация: 24.06.2012
Сообщений: 662
Записей в блоге: 5
Завершенные тесты: 1
20.11.2012, 20:18  [ТС] #6
а точно, а я и не заметил)затуп)
0
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
20.11.2012, 20:18
Привет! Вот еще темы с ответами:

Простая и интересная задачка по C++: объяснить почему результат работы программы именно такой, какой он есть - C++
Всем привет, я сам ещё новичок в C++(&lt; 2 лет изучаю), но уже что-то понимаю и решил сделать задачу на основы языка для совсем зелёных, для...

Интересная задачка с битовыми операторами, флагами, переменными, или "до меня не дошло письмо из штаба" - C++
Дорогие форумчане! Недавно я занялся исправлять пробелы в знании C++ одной замечательной книжкой, которую мне помогли найти! Книжка...

Интересная конструкция в C++ - C++
Добрый день. Подскажите пожалуйста, что это такое: float time = clock.getElapsedTime().asMicroseconds();

Интересная штука - C++
Интересная штука происходит. Создал я значит сетевое приложение, ну естественно подключена ws2_32.lib. Так вот, даже закомпилированная в...


Искать еще темы с ответами

Или воспользуйтесь поиском по форуму:
Yandex
Объявления
20.11.2012, 20:18
Ответ Создать тему
Опции темы

КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2017, vBulletin Solutions, Inc.
Рейтинг@Mail.ru