VPF::[C++] Сортировка_2 - Форум программистов

KatrinIceLand

Дата 6.9.2008, 19:29 (ссылка)

(нет голосов)

Загрузка ...

Бывалый

Профиль
Группа: Участник
Сообщений: 166
Регистрация: 16.3.2006

Репутация: нет
Всего: нет

Всем опять привет. Вот у меня еще одна задачка на сортировку (та же тема что и в теме "Сортировка")

Задание:

Цитата

Dorothy is a shopaholic. Whenever there is a discount of the kind where you can buy three items and only pay for two, she goes completely mad and feels a need to buy all items in the store. You have given up on curing her for this disease, but try to limit its effect on her wallet.

You have realized that the stores coming with these offers are quite selective when it comes to which items you get for free; it is always the cheapest ones. As an example, when your friend comes to the counter with seven items, costing 400, 350, 300, 250, 200, 150, and 100 dollars, she will have to pay 1500 dollars. In this case she got a discount of 250 dollars. You realize that if she goes to the counter three times, she might get a bigger discount. E.g. if she goes with the items that costs 400, 300 and 250, she will get a discount of 250 the first round. The next round she brings the item that costs 150 giving no extra discount, but the third round she takes the last items that costs 350, 200 and 100 giving a discount of an additional 100 dollars, adding up to a total discount of 350.

Your job is to find the maximum discount Dorothy can get.

Input specification

The first line of input gives the number of test scenarios, 1 ≤ t ≤ 20. Each scenario consists of two lines of input. The first gives the number of items Dorothy is buying, 1 ≤ n ≤ 20000. The next line gives the prices of these items, 1 ≤ pi ≤ 20000.
Output specifications

For each scenario, output one line giving the maximum discount Dorothy can get by selectively choosing which items she brings to the counter at the same time.
Sample input
1
6
400 100 200 350 300 250
Sample output
400

А код все тот же:

Код


#include <iostream>         // cin, cout
#include <string>           // Strings, find()
#include <algorithm>        // sort

using namespace std;

const int MAX_n = 10000;

int main() {
    int t; cin >> t;
    while (t--) {  // For each test case
        // Input data
        int n; cin >> n;
        string P[MAX_n];
        for (int i = 0; i < n; j++) {
            cin >> P[i];
        }

        sort(P, P + n);     // sort

        // Test for prefixes in the list
        bool ok = true; 
        for (int i = 0; i < n-1; i++) {
            int indx = P[i+1].find(P[i],0);
            if (indx == 0) {
               ok = false;
            }
        }

        // Output result
        if (ok) cout << "NO\n";
        else    cout << "YES\n";
    }
}

Поможите?

--------------------

[... кто изобрел математику? А зачем?...

KatrinIceLand

Дата 7.9.2008, 17:45 (ссылка)

(нет голосов)

Загрузка ...

Бывалый

Профиль
Группа: Участник
Сообщений: 166
Регистрация: 16.3.2006

Репутация: нет
Всего: нет

Какой алгоритм лучше для это?

Каждая 3-я вещь бесплатно, конечно же самая дешевая

1 - самая дешевая из 3х
6 - всего 6 вещей выбрано

Надо что бы Дороти получила максимальную скидку.

Если она выбрала

1
6
400 100 200 350 300 250

Тогда она подойдет 3 раза с:

250 200 100

400 350 300

и получит 100 + 300 скидку smile

За третью вещь.

Это сообщение отредактировал(а) KatrinIceLand - 7.9.2008, 17:49

--------------------

[... кто изобрел математику? А зачем?...

KatrinIceLand

Дата 7.9.2008, 18:38 (ссылка)

(нет голосов)

Загрузка ...

Бывалый

Профиль
Группа: Участник
Сообщений: 166
Регистрация: 16.3.2006

Репутация: нет
Всего: нет

Вот я отсортировала элементы:

Код


const int MAX_n = 20000;

int main() {

    ofstream output("outex");

    int array[] = { 400, 100, 200, 350, 300, 250 };
    int elements = sizeof(array) / sizeof(array[0]); 
       sort(array, array + elements);
       for (int i = 0; i < elements; ++i)
    
    //cout << array[i] << ' ';
    output << array[i];

output: 100200250300350400, как мне теперь выбрать 1й + 4й и вывести ответ? И вообще я правильным путем иду?

Это сообщение отредактировал(а) KatrinIceLand - 7.9.2008, 18:47

--------------------

[... кто изобрел математику? А зачем?...

Dov

Дата 7.9.2008, 19:55 (ссылка)

(нет голосов)

Загрузка ...

аСинизатор

Профиль
Группа: Завсегдатай
Сообщений: 1721
Регистрация: 10.5.2003
Где: Эрец-Исраэль

Репутация: 50
Всего: 88

KatrinIceLand, я бы сделал так:

1. Отсортировал бы в порядке убывания.
2. Подсчитал бы в цикле максимальную сумму скидки. Например так:

Код

int discount  = 0;
for(int i = 2; i < elements; i += 3)
     discount  += array[i];

--------------------

Тут вечности запах томительный,
И свежие фрукты дешевые,
А климат у нас – изумительный,
И только соседи – #уевые.
Игорь Губерман.

KatrinIceLand

Дата 7.9.2008, 19:59 (ссылка)

(нет голосов)

Загрузка ...

Бывалый

Профиль
Группа: Участник
Сообщений: 166
Регистрация: 16.3.2006

Репутация: нет
Всего: нет

Код


const int MAX_n = 20000;

int main() {
    int t; cin >> t;
    int sum;
    while (t--) {  
        // Input data
        int n; cin >> n;
        string P[MAX_n];
        for (int i = 0; i < n; i++) {
            cin >> P[i];
        }

        sort(P, P + n);        
         for (int i = 0; i < n; ++i)
             sum = P[i].find(P[0]+P[3]);

         cout << sum;
    }

Что не так?

Добавлено через 2 минуты и 42 секунды
Dov, привет.

Спасибо за помощь smile

Цитата(Dov @ 7.9.2008, 19:55

)

Подсчитал бы в цикле максимальную сумму скидки. Например так:

Не очень уловила ход мысли. Можно подоходчивее smile

--------------------

[... кто изобрел математику? А зачем?...

Dov

Дата 7.9.2008, 20:15 (ссылка)

(нет голосов)

Загрузка ...

аСинизатор

Профиль
Группа: Завсегдатай
Сообщений: 1721
Регистрация: 10.5.2003
Где: Эрец-Исраэль

Репутация: 50
Всего: 88

KatrinIceLand, смотри.

1. сортируем в порядке убывания. получаем: 400, 350, 300, 250, 200,100.
2. подсчитываем в цикле(см. мой цикл), начиная с элемента array[2], сумму скидки. получаем 300 + 100 = 400.

--------------------

KatrinIceLand

Дата 7.9.2008, 20:17 (ссылка)

(нет голосов)

Загрузка ...

Бывалый

Профиль
Группа: Участник
Сообщений: 166
Регистрация: 16.3.2006

Репутация: нет
Всего: нет

что то тут не так smile

Код


int main() {
    int t; cin >> t;
    int discount = 0;
    while (t--) {  // For each test case
        // Input data
        int n; cin >> n;
        string P[MAX_n];
        for (int i = 0; i < n; i++) {
            cin >> P[i];
        }

        sort(P, P + n);  
        for(int i = 2; i < n; i += 3)
        discount += i;

     cout << discount;
    }

подскажите пожалуйста smile

Это сообщение отредактировал(а) KatrinIceLand - 7.9.2008, 20:18

--------------------

[... кто изобрел математику? А зачем?...

Dov

Дата 7.9.2008, 20:21 (ссылка)

(нет голосов)

Загрузка ...

аСинизатор

Профиль
Группа: Завсегдатай
Сообщений: 1721
Регистрация: 10.5.2003
Где: Эрец-Исраэль

Репутация: 50
Всего: 88

можно такой цикл написать, что бы не менять порядок сортировки:

Код

for(int i = elements - 3; i >= 0; i -= 3)
    discount  += array[i];

--------------------

KatrinIceLand

Дата 7.9.2008, 20:47 (ссылка)

(нет голосов)

Загрузка ...

Бывалый

Профиль
Группа: Участник
Сообщений: 166
Регистрация: 16.3.2006

Репутация: нет
Всего: нет

Dov, спасибо! С постоянными числами в массиве получилось, я теперь пытаюсь запустить все то же только уже без данных в массиве. Т.е. что бы данные считывались и обрабатывались. Что то у меня не совсем получается. Может ты увидишь ошибку?

Код


const int MAX_n = 20000;

int main() {
    int discount = 0;
    int t; cin >> t;
    while (t--) {  // For each test case
        // Input data
        int n; cin >> n;
        string P[MAX_n];
        for (int i = 0; i < n; i++) {
            cin >> P[i];
        }
        sort(P, P + n);
        for (int i = 0; i < n; i++)
            //sorted = P[i];           //тут надо куда то все это сохранить
            for (int i = n-3; i >= 0; i -= 3)
                discount += P[i];    //и так компилятору не нравится
          
    cout << discount;

Это сообщение отредактировал(а) KatrinIceLand - 7.9.2008, 21:03

--------------------

[... кто изобрел математику? А зачем?...

Dov

Дата 7.9.2008, 21:54 (ссылка)

(нет голосов)

Загрузка ...

аСинизатор

Профиль
Группа: Завсегдатай
Сообщений: 1721
Регистрация: 10.5.2003
Где: Эрец-Исраэль

Репутация: 50
Всего: 88

Ну, что-то такое, например:

Код

const int MAX_n = 10000;

int main()
{
    string P[MAX_n];
    int discount;
    int t, n;

    cout << "Enter t: ";
    cin >> t;
    
    while (t--)
    {  // For each test case
        // Input data
        cout << "Enter n: ";
        cin >> n;
        
        for (int i = 0; i < n; i++)
        {
            cout << "Enter P[" << i << "] = ";
            cin >> P[i];
        }

        sort(P, P + n);
        
        discount = 0;
        for (int i = n - 3; i >= 0; i -= 3)
            discount += atoi(P[i].c_str());    
          
        cout << "discount = " << discount << endl << endl;
    }

    return 0;
}

--------------------

KatrinIceLand

Дата 7.9.2008, 22:06 (ссылка)

(нет голосов)

Загрузка ...

Бывалый

Профиль
Группа: Участник
Сообщений: 166
Регистрация: 16.3.2006

Репутация: нет
Всего: нет

вот тут все правильно:

Код


const int MAX_n = 20000;
int main() {
    int discount = 0;
    int t; cin >> t;
    while (t--) {  // For each test case
        // Input data
        int n; cin >> n;
        string P[MAX_n];
        for (int i = 0; i < n; i++) {
            cin >> P[i];
        }
        sort(P, P + n);

а вот здесь надо что то доделать:

Код


 for (int i = 0; i < n; i++)
            //sorted = i;           //тут надо куда то все это сохранить
            for (int i = n-3; i >= 0; i -= 3)
                discount += i;    
          
    cout << discount;

Это сообщение отредактировал(а) KatrinIceLand - 7.9.2008, 22:07

--------------------

[... кто изобрел математику? А зачем?...

Dov

Дата 7.9.2008, 22:09 (ссылка)

(нет голосов)

Загрузка ...

аСинизатор

Профиль
Группа: Завсегдатай
Сообщений: 1721
Регистрация: 10.5.2003
Где: Эрец-Исраэль

Репутация: 50
Всего: 88

KatrinIceLand, что нужно сохранить, куда и для каких целей? Говори конкретнее. smile

--------------------

KatrinIceLand

Дата 7.9.2008, 22:34 (ссылка)

(нет голосов)

Загрузка ...

Бывалый

Профиль
Группа: Участник
Сообщений: 166
Регистрация: 16.3.2006

Репутация: нет
Всего: нет

Цитата(Dov @ 7.9.2008, 22:09

)

KatrinIceLand, что нужно сохранить, куда и для каких целей? Говори конкретнее. smile

Нет, я не так выразилась, в смысле сортируем, присваиваем это значение какой-то переменной, потом берем первый и 4й элемент в массиве, складываем и выводим общий discount smile

--------------------

[... кто изобрел математику? А зачем?...

Dov

Дата 7.9.2008, 23:15 (ссылка)

(нет голосов)

Загрузка ...

аСинизатор

Профиль
Группа: Завсегдатай
Сообщений: 1721
Регистрация: 10.5.2003
Где: Эрец-Исраэль

Репутация: 50
Всего: 88

KatrinIceLand, я не очень понимаю, зачем нужна какая-то переменная.
Тебе нужен ещё один массив целых чисел?

После сортировки мы и так можем сложить сумму максимальной скидки. Зачем дополнительные переменные?

--------------------

KatrinIceLand

Дата 7.9.2008, 23:18 (ссылка)

(нет голосов)

Загрузка ...

Бывалый

Профиль
Группа: Участник
Сообщений: 166
Регистрация: 16.3.2006

Репутация: нет
Всего: нет

Ок, не надо переменной. Но все равно где-то ошибка.
Вот что у меня на данный момент:

Код


int main() {
    
    int discount = 0;
    int t; cin >> t;
    while (t--) {  // For each test case
        // Input data
        int n; cin >> n;
        string P[MAX_n];
        for (int i = 0; i < n; i++) {
            cin >> P[i];
        }
        sort(P, P + n);
        for (int i = 0; i < n; i++)
            for (int j = n-3; j >= 0; j -= 3)
                discount += j;
          
    cout << discount;
    }
}

Добавлено через 1 минуту и 32 секунды
Dov, классный у тебя аватар smile

--------------------

[... кто изобрел математику? А зачем?...

0 Пользователей читают эту тему (0 Гостей и 0 Скрытых Пользователей)
0 Пользователей:
« Предыдущая тема \| Центр помощи \| Следующая тема »