Версия для печати темы
Нажмите сюда для просмотра этой темы в оригинальном формате
Форум программистов > Центр помощи > [C++] Сортировка_2


Автор: KatrinIceLand 6.9.2008, 19:29
Всем опять привет. Вот у меня еще одна задачка на сортировку (та же тема что и в теме "Сортировка")

Задание:
Цитата

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
 smile Какой алгоритм лучше для это?

Каждая 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, 18:38
Вот я отсортировала элементы:

Код

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й и вывести ответ? И вообще я правильным путем иду?

Автор: Dov 7.9.2008, 19:55
KatrinIceLand, я бы сделал так:

1. Отсортировал бы в порядке убывания.
2. Подсчитал бы в цикле максимальную сумму скидки. Например так:
Код
int discount  = 0;
for(int i = 2; i < elements; i += 3)
     discount  += array[i];

Автор: KatrinIceLand 7.9.2008, 19:59
Код

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
KatrinIceLand, смотри.

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

Автор: KatrinIceLand 7.9.2008, 20:17
что то тут не так  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 

Автор: Dov 7.9.2008, 20:21
можно такой цикл написать, что бы не менять порядок сортировки:
Код
for(int i = elements - 3; i >= 0; i -= 3)
    discount  += array[i];

Автор: KatrinIceLand 7.9.2008, 20:47
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;

Автор: Dov 7.9.2008, 21:54
Ну, что-то такое, например:
Код
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
 smile 
вот тут все правильно:
Код

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;

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

Автор: KatrinIceLand 7.9.2008, 22:34
Цитата(Dov @  7.9.2008,  22:09 Найти цитируемый пост)
KatrinIceLand, что нужно сохранить, куда и для каких целей? Говори конкретнее.  smile  

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

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

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

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

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 

Автор: Dov 7.9.2008, 23:29
KatrinIceLand, а ты смотришь примеры, которые я тебе даю? Зачем ты делаешь двойной цикл? 
Вот тебе ещё один пример. Никаких ошибок там нет. Сумму скидки считает правильно.
Код
bool Greater( string a, string b )
{
   return atoi(a.c_str()) > atoi(b.c_str());
}

int main() {
    
    int discount;
    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, Greater);
        
        discount = 0;
        for (int i = 2; i < n; i += 3)         
             discount += atoi(P[i].c_str());
          
    cout << discount << endl;
    }
}

Автор: KatrinIceLand 7.9.2008, 23:36
Dov, спасибо за помощь!

Но тут не все так просто, я на сайте эту программу должна сдать, и там все это не принимается  smile 

VS - счастлив  smile, ошибок нет, все отлично.. Только вот на сайте программа говорит: CompileTimeError

Автор: Dov 7.9.2008, 23:58
А твоя задача в чём заключается?

 Написать программу "с нуля" или тебе даётся какая-то программа, а ты должна её привести в надлежащий вид? 

Автор: KatrinIceLand 8.9.2008, 00:09
Код


//вот что дается
#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";
    }
}

Автор: Dov 8.9.2008, 00:15
KatrinIceLand, а ты уверена, что этот код дан, именно, для этой задачи?

Автор: KatrinIceLand 8.9.2008, 00:22
Цитата(Dov @  8.9.2008,  00:15 Найти цитируемый пост)
KatrinIceLand, а ты уверена, что этот код дан, именно, для этой задачи?

Я уже не в чем не уверена  smile Но препод дал этот код для 3х похожих программ, для телефонов и для расчета скидок. До третьей я так и не дошла..

Меня этот сайт на котором я сдаю программу уже достал. Не понимаю я что ему еще нужно.. На моем компе все компилируется, результат правильный, а на сайте ошибка  smile 

Ладно, поздно уже, устала я биться с HighTeh.. Всем огромное спасибо за помощь!!!  smile 

И спокойной ночи  smile 

Автор: Dov 8.9.2008, 00:26
Спокойной ночи, KatrinIceLand.  smile

Добавлено через 2 минуты и 47 секунд
Ты бы спросила у препода, что можно использовать в написании программы, а что нельзя. А то бродим здесь, как слепые котята..  smile 

Автор: KatrinIceLand 8.9.2008, 00:48
Договорились! Я обязательно решения выложу, что бы разобраться что к чему  smile  Если конечно он нам их вышлет  smile 

Автор: KatrinIceLand 11.9.2008, 14:15
А вот вариант который все таки принял сайт. Найди 3 отличия:
Код

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

using namespace std;

const int MAX_n = 20000;

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


Я такие варианты миллион раз пыталась сдать, а он ни в какую, зато под четким вниманием преподавателя, все получилось. А ошибка с newline ... возможно просто пустая строка в конце программы, надо сделать backspace до самой последней скобки.  smile  бред...

Автор: Dov 11.9.2008, 16:37
Цитата(KatrinIceLand @  11.9.2008,  14:15 Найти цитируемый пост)
Найди 3 отличия:

Вот самое главное отличие:
Код
int P[MAX_n];


Цитата(Dov @  8.9.2008,  00:15 Найти цитируемый пост)
KatrinIceLand, а ты уверена, что этот код дан, именно, для этой задачи?

Не зря я это спрашивал. Твой string спутал все карты.  smile  Сортировка не получалась, и мне пришлось писать дополнительную ф-цию, что не требовалось по условию задачи.  smile 

Автор: Damarus 11.9.2008, 17:02
Цитата(KatrinIceLand @  11.9.2008,  15:15 Найти цитируемый пост)
Я такие варианты миллион раз пыталась сдать, а он ни в какую, зато под четким вниманием преподавателя, все получилось. А ошибка с newline ... возможно просто пустая строка в конце программы, надо сделать backspace до самой последней скобки.  smile  бред... 

Ты бы хоть ошибки полностью написала smile 

Автор: KatrinIceLand 11.9.2008, 17:07
Цитата(Dov @  11.9.2008,  16:37 Найти цитируемый пост)
Не зря я это спрашивал. Твой string спутал все карты.  smile  Сортировка не получалась, и мне пришлось писать дополнительную ф-цию, что не требовалось по условию задачи.  smile 

Совершенно точно, string не должно было быть, sorry  smile 

Цитата(Damarus @  11.9.2008,  17:02 Найти цитируемый пост)
Ты бы хоть ошибки полностью написала smile  

1. String
2. Пустая строка в конце кода

Powered by Invision Power Board (http://www.invisionboard.com)
© Invision Power Services (http://www.invisionpower.com)