Форум программистов [Powered by Invision Power Board]

Версия для печати темы
Нажмите сюда для просмотра этой темы в оригинальном формате

Форум программистов > Центр помощи > [C++]есть решение, нуна разобрать

Автор: CppDevelopeR 16.4.2008, 16:11

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

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

Формат входных данных

Во входном файле задано сначала число N (1≤N≤1000), а затем N чисел - стоимости выбранных Васей товаров. Все стоимости - натуральные числа, не превышающие 10000.

Формат выходных данных

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

Вот решение:

Код


#include <iostream>
using namespace std;

int main()
{
    int n, arr[1000], i, j, a;
    cin>>n;
    for(i=0;i<n;i++) cin>>arr[i];
    for(i=0;i<n;i++)
    {
        for(j=0;j<n-1;j++)
        {
            if(arr[j]<arr[j+1])
            {
                a=arr[j];
                arr[j]=arr[j+1];
                arr[j+1]=a;
            }
        }
    }
    for(i=a=0;i<n;i++)
    {
        if((i+1)%3)
        {
            a+=arr[i];
        }
    }
    cout<<endl<<a<<endl;
    return 0;
}

Нужно сделать разбор этой задачи. Помогите плиз, сделайте разбор. Очень срочно! Ведь наверна не трудно, есть же решение!

Автор: orthrus 16.4.2008, 16:26

Я что-то не понял, каким образом нужно разобрать? Или объяснить как эта программа работает?

Автор: THandle 16.4.2008, 16:47

Помойму это пузырьковая сортировка...

Вот тук кратенькое описание я давал - http://forum.vingrad.ru/faq/topic-200441.html

Автор: CppDevelopeR 16.4.2008, 17:29

при чем здесь сортировка? нуна задачу разобрать. Ну там как решал и т.д.

Добавлено через 11 минут и 24 секунды
Ну да, ну типо обьяснить способ решения там, как она работает и т.п.

Добавлено через 11 минут и 41 секунду
но сортирова здесь есть

Автор: mr.Anderson 16.4.2008, 21:22

Собственно решение сидит в этом куске:

Код


for(i=a=0;i<n;i++)
    {
        if((i+1)%3)
        {
            a+=arr[i];
        }
    }

Остальное к делу вообще не относится. Но вот смысл этого куска еще понять надо... Вот что мне всегда не нравилось в авторских решениях олимпиадных задач: решение сверхкороткое, а вот прежде чем его смысл поймешь, не один день пройдет... Если вообще поймешь...

По сути, здесь проходят по ранее упорядоченному списку цен товаров и выбирают каждый третий элемент. Выбираемые значения суммируют. Только не понятно, почему именно эти элементы.

Автор: mr.Anderson 16.4.2008, 21:41

А! Въехал.

Добавлено @ 21:42
Так вот. Упорядочивание происходит по убыванию, и это правильно. Читаем еще раз условие: каждый третий товар бесплатно (поэтому ищем каждый третий элемент), причем из трех товаров оплачиваются два наиболее дорогих (то есть если цены троек товаров упорядочены по убыванию, то из тройки третий элемент будет самым дешевым, то есть за него нужно будет платить). Поэтому ищем каждый третий элемент и суммируем их друг с другом, после чего получим минимальную цену.

Интересное решение.

Автор: CppDevelopeR 16.4.2008, 21:53

Да я вот решил, это с олимпиады зимней, сказали разобрать, а вы же знаете какая у мя память.

Добавлено через 3 минуты и 23 секунды
А я человек занятой...

Автор: Torgot 17.4.2008, 03:58

Суммируеца не каждый 3-й элемент а все кроме кратных 3-м

Автор: mr.Anderson 17.4.2008, 20:36

Torgot, нет, именно каждый третий. Проверяется I, а не a[I].

CppDevelopeR, имей привычку благодарить за помощь. Хотя бы словесно. А то с отношением "я человек занятой" ты скоро эту помощь вообще получать перестанешь. Я лично уже точно помогать не буду. Ты говоришь так, как будто все тут дурью маются, только ты один занят по уши.

Помогли - умей сказать "спасибо".

Понижаю репутацию.

Автор: Torgot 18.4.2008, 14:54

Нет все кроме кратных 3-м

Код


for(i=a=0;i<n;i++)
    {
        if((i+1)%3) 
        {
            a+=arr[i];
        }
    }

Только тогда когда остаток от деления (i+1) на 3 не равен 0 происходит вход в блок.

Автор: mr.Anderson 19.4.2008, 14:09

Torgot, а это не будет каждый третий? Кратны трем номера 3, 6, 9, 12, 15, 18 ... Я не прав? Это одно и то же, что кратные трем, что каждый третий. Чего спорим-то?

Автор: Torgot 19.4.2008, 17:30

Цитата

из тройки третий элемент будет самым дешевым, то есть за него нужно будет платить). Поэтому ищем каждый третий элемент и суммируем их друг с другом, после чего получим минимальную цену

Если я правильно понял то у тебя написано с точностью на оборот

Автор: opjox 19.4.2008, 18:19

Собственно, как и требует условие задачи, оплачиваются два самых дорогих предмета. Т.о. суммируются все элементы, кроме третьих, т.е. как это говорит Torgot.

В этом очень легко наглядно убедиться. Напишем так:

Код


#include <iostream>

int main()
{
  const int n = 20;
  for(int i=0; i<n; i++) {
    if((i+1)%3) std::cout << i+1 /*индексацию будем вести с 1*/ << " ";
  }
  return 0;
}

Вывод программы:

Код


1 2 4 5 7 8 10 11 13 14 16 17 19 20