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

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

Войти
Регистрация
Восстановить пароль
 
Fennec
1 / 1 / 0
Регистрация: 10.02.2010
Сообщений: 36
#1

Задача о стульях - C++

20.01.2016, 20:44. Просмотров 364. Ответов 2
Метки нет (Все метки)

Итак, следуя хорошей манере создавать по теме на задачу, продолжим.

 Комментарий модератора 
П.5.18.Правил
Запрещено размещать задания и решения в виде картинок и других файлов с их текстом.


Вот сама задача:
«Где бы выгодно купить стулья, а потом выгодно их продать» — думал Остап после неудачной погони за 12 стульями.
Он решил подзаработать себе на билет до Рио продажей мебели. Прежде чем начать работу, он решил понаблюдать за происходящим и придумать, как побольше заработать.
Остап узнал, что в городе все продавцы продают только по одному стулу, и каждый покупатель готов купить не более одного. Всего он нашел N предложений, стоимость стула у i-го из продавцов равна Ai рублей, конечно, цены могут отличаться. Кроме того, он нашёл M потенциальных покупателей, каждый из которых может купить стул не дороже Bi рублей. При этом сам Остап может купить и продать любое количество товара.
Остап хочет получить наибольшую прибыль, поэтому он обратился за помощью к вам. Определите максимальную прибыль, которую он может получить.

Формат ввода:

Первая строка входных данных содержит два целых числа N, M (1 ≤ N, M ≤ 105) — количество предложений и количество потенциальных покупателей соответственно.

Вторая строка содержит N целых чисел Ai (0 ≤ Ai ≤ 109) цены, по которым продавцы готовы продавать стулья.

Третья строка содержит M целых чисел Bi (0 ≤ Bi ≤ 109) суммы, которые потенциальные покупатели готовы отдать при покупке стула.

Формат вывода:

Выведите одно целое число равное максимальной прибыли, которую Остап может получить.

Пример:

Ввод:
6 5
5 10 8 4 7 2
3 1 11 18 9

Вывод:
27
Вот мое решение:
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
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
#include <iostream>
#include <fstream>
#include <vector>
#include <algorithm> 
#include <functional>
 
using namespace std;
 
int main()
{
    ifstream input("input.txt");
 
    int sellersNumber = 0;
    int buyersNumber = 0;
 
    input >> sellersNumber;
    input >> buyersNumber;
 
    vector<int> sellPrices(sellersNumber);
    vector<int> buyPrices(buyersNumber);
 
    for (int i = 0; i < sellersNumber; i++)
    {
        input >> sellPrices[i];
    }
 
    for (int i = 0; i < buyersNumber; i++)
    {
        input >> buyPrices[i];
    }
 
    input.close();
 
    sort(sellPrices.begin(), sellPrices.end());
    sort(buyPrices.begin(), buyPrices.end(), std::greater<int>());
 
    int result = 0;
    int minRange = min(sellPrices.size(), buyPrices.size());
 
    for (int i = 0; i < minRange; i++)
    {
        int profit = buyPrices[i] - sellPrices[i];
        if (profit > 0)
        {
            result += profit;
        }
    }
 
    ofstream output("output.txt");
    output << result;
    output.close();
 
    return 0;
}
логика простецкая: мы не можем получить прибыль покупая дороже чем продаем. В системе проходит 19 тестов, после чего падает. Что я делаю не так?
0
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
20.01.2016, 20:44
Здравствуйте! Я подобрал для вас темы с ответами на вопрос Задача о стульях (C++):

Задача о спящем парикмахере, посетителях и свободных стульях - C#
В парикмахерской расположено единственное кресло, на котором спит парикмахер, и несколько стульев для клиентов. Когда клиент приходит в...

Задача о спящем парикмахере, посетителях и свободных стульях (готовый код) - C++ Builder
#include&lt;windows.h&gt; //--------------------------------------------------------------------------- int yshed = 0; ...

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

Задача на перебор вариантов. Задача Л.Эйлера. Про чиновника - PascalABC.NET
Задача Л.Эйлера. Некий чиновник купил лошадей и быков на сумму 1770 талеров. За каждую лошадь он уплатил по 31 талеру, а за каждого быка по...

Задача на k-тую цифру последовательности, задача на схему Горнера. - Pascal
Ну, собственно опять прошу помощи... Задача 1: Определить k-тую цифру последовательности 1234567891011121314…, в которой выписаны подряд...

Первая смешанная задача для волнового уравнения на отрезке (задача о колебаниях ограниченной струны) методом Фурье - Дифференциальные уравнения
Решить первую смешанную задачу для волнового уравнения на отрезке (задача о колебаниях ограниченной струны) методом Фурье ...

Надоела реклама? Зарегистрируйтесь и она исчезнет полностью.
Fennec
1 / 1 / 0
Регистрация: 10.02.2010
Сообщений: 36
21.01.2016, 10:16  [ТС] #2
Добавлено через 56 минут
Закрывайте тему, я разобрался где накосячил.

Значение результата должно было быть типа long long int, чтобы вместить в себя нужный диапазон значений. Поверить не могу, что мог на этом проколоться.
0
Mr.X
Эксперт С++
3049 / 1694 / 265
Регистрация: 03.05.2010
Сообщений: 3,867
21.01.2016, 10:21 #3
Цитата Сообщение от Fennec Посмотреть сообщение
логика простецкая
Цитата Сообщение от Fennec Посмотреть сообщение
Значение результата должно было быть типа long long int, чтобы вместить в себя нужный диапазон значений
Fennec, так что не логикой единой! Чуйку надо иметь!
0
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
21.01.2016, 10:21
Привет! Вот еще темы с ответами:

Задача о размещении весов по ящикам (задача о рюкзаках) - Delphi
Есть упорядоченный по невозрастанию набор весов предметов w1..wn, которые необходимо распределить по ящикам способным выдержать вес V,...

Задача Дам или задача Восьми - Алгоритмы
помогите найти ошибку в алгоритме. не находит ответ подозреваю ошибку в k, i, j package com.company; import java.util.Arrays;...

Задача на файл и задача на создание очереди - Pascal
1 Дан символьный файл, содержащий, по крайней мере, один символ пробела. Удалить из файла все символы, предшествующие пробелу 2 ...

Задача линейного программирования, транспортная задача - Методы оптимизации
Всем привет. сижу на экзамене, помогите пожалуйста решить,сроно!!! заранее спасибо.


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

Или воспользуйтесь поиском по форуму:
Ответ Создать тему
Опции темы

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