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

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

Восстановить пароль Регистрация
 
ZaMaZaN4iK
Мой лучший друг-отладчик!
 Аватар для ZaMaZaN4iK
163 / 163 / 9
Регистрация: 24.06.2012
Сообщений: 662
Записей в блоге: 5
Завершенные тесты: 1
20.11.2012, 16:26     Интересная задачка(оптимизация) #1
Вот недавно писал районку по информатике.И там была такая вот задача.Я то её решил, но у меня даже ввод чисел из некоторых тестов не проходит.Прошу вас, как более опытных программистов, помочь мне её оптимизировать.
Вот условие задачи:
Задача 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;
}
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
20.11.2012, 16:26     Интересная задачка(оптимизация)
Посмотрите здесь:

C++ интересная головоломка
C++ Интересная сортировка
C++ Интересная задачка
Интересная штука C++
C++ Интересная задачка, и блок схема нужна С++
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
valeriikozlov
Эксперт C++
 Аватар для valeriikozlov
4660 / 2486 / 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.
ZaMaZaN4iK
Мой лучший друг-отладчик!
 Аватар для ZaMaZaN4iK
163 / 163 / 9
Регистрация: 24.06.2012
Сообщений: 662
Записей в блоге: 5
Завершенные тесты: 1
20.11.2012, 19:17  [ТС]     Интересная задачка(оптимизация) #3
valeriikozlov, ваш способ очень интересен, сейчас его попробую.Но вот проблема в чём есть ещё - у меня по времени не проходит даже считывание знчений с файла!У меня лимит 2 секунды, а считывание файла со значениями( файл весит 5.5 мб - предсталяете я думаю, сколько там чисел.И их кол-во к сожалению влазаят в ограничение) занимает примерно 6 секунд.Что с этим делать?
LineStown
 Аватар для LineStown
63 / 63 / 3
Регистрация: 04.08.2010
Сообщений: 399
20.11.2012, 19:23     Интересная задачка(оптимизация) #4
Цитата Сообщение от ZaMaZaN4iK Посмотреть сообщение
Ограничение по памяти: 256 мегабайт Ввод: с клавиатуры
В условии как бы ввод с клавиатуры) Соответственно 2 секунды на расчет, а не на считывание из файла.)
diagon
Higher
 Аватар для diagon
1920 / 1186 / 49
Регистрация: 02.05.2010
Сообщений: 2,925
Записей в блоге: 2
20.11.2012, 19:58     Интересная задачка(оптимизация) #5
Используйте scanf/printf вместо cin/cout.
Если совсем плохо, то fread с ручным парсингом.
ZaMaZaN4iK
Мой лучший друг-отладчик!
 Аватар для ZaMaZaN4iK
163 / 163 / 9
Регистрация: 24.06.2012
Сообщений: 662
Записей в блоге: 5
Завершенные тесты: 1
20.11.2012, 20:18  [ТС]     Интересная задачка(оптимизация) #6
а точно, а я и не заметил)затуп)
Yandex
Объявления
20.11.2012, 20:18     Интересная задачка(оптимизация)
Ответ Создать тему
Опции темы

Текущее время: 19:50. Часовой пояс GMT +3.
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2016, vBulletin Solutions, Inc.
Рейтинг@Mail.ru