Форум программистов, компьютерный форум, киберфорум
С++ для начинающих
Войти
Регистрация
Восстановить пароль
 
Рейтинг 4.67/6: Рейтинг темы: голосов - 6, средняя оценка - 4.67
4 / 4 / 2
Регистрация: 23.12.2016
Сообщений: 124
1

Поиск минимальной суммы троек входных значений

26.05.2018, 23:32. Просмотров 1073. Ответов 3
Метки нет (Все метки)

Имеется набор данных, состоящий из троек положительных целых чисел. Необходимо выбрать из каждой тройки ровно одно число так, чтобы сумма всех выбранных чисел была четной и при этом минимально возможной. Если получить требуемую сумму невозможно, в качестве ответа нужно выдать 0.
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
55
56
57
#include "stdafx.h"
#include <iostream>
 
using namespace std;
 
int main()
{
    int n;
    int a, b, c;
    int minRaz = 1000000;
    int minSum = 0;
 
    cin >> n;
 
    for (int i = 0; i < n; i++) {
 
        cin >> a >> b >> c;
        
        if (a <= b && a <= c) {
            if ( (b - a) < minRaz && (b - a) % 2 == 0)
                minRaz = (b - a);
            if ( (c - a) < minRaz && (c - a) % 2 == 0)
                minRaz = (c - a);
            minSum += a;
        }
 
        if (b <= a && b <= c) {
            if ( (a - b) < minRaz && (a - b) % 2 == 0)
                minRaz = (a - b);
            if ( (c - b) < minRaz && (c - b) % 2 == 0)
                minRaz = (c - b);
            minSum += b;
        }
 
        if (c <= a && c <= b) {
            if ( (a - c) < minRaz && (a - c) % 2 == 0)
                minRaz = (a - c);
            if ( (b - c) < minRaz && (b - c) % 2 == 0)
                minRaz = (b - c);
            minSum += c;
        }
    }
 
    if (minRaz == 1000000) {
        cout << '0';
        return 0;
    }
 
    if (minSum % 2 == 0) {
        cout << minSum;
    }
    else if (minSum % 2 == 1) {
        cout << minSum + minRaz;
    }
    system("pause");
    return 0;
}
0
Programming
Эксперт
94731 / 64177 / 26122
Регистрация: 12.04.2006
Сообщений: 116,782
26.05.2018, 23:32
Ответы с готовыми решениями:

Поиск минимальной суммы строк
Вычислить сумму элементов каждой строки матрицы Х (5,5). Определить наименьшее значение этих сумм и...

Поиск минимальной и средней суммы
как найти минимальную суммарную и минимальную среднюю зарплаты? package zadanie_2; import...

Поиск минимальной суммы в дереве
Здравствуйте! Есть дерево и необходимо найти минимальную сумму в дереве, т.е. от корня до листа....

Поиск минимальной суммы строки в матрице
Есть такая задача, нужно создать матрицу 3х4, и найти строку с минимальной суммой в строке, с...

3
469 / 422 / 290
Регистрация: 10.03.2015
Сообщений: 1,782
27.05.2018, 02:20 2
Цитата Сообщение от WWH Посмотреть сообщение
Необходимо выбрать из каждой тройки ровно одно число так, чтобы сумма всех выбранных чисел была четной и при этом минимально возможной
Я не понимаю. Мы выбираем одно число, а считаем сумму каких-то всех?

Сумма всех чисел каждой тройки будет всегда одинакова, от перестановки слагаемых - сумма не меняется.
Четная еще ладно, но минимально возможной это как?!

Объясните на примере, что вы хотите получить и как понимать эту задачу?
0
4 / 4 / 2
Регистрация: 23.12.2016
Сообщений: 124
27.05.2018, 08:33  [ТС] 3
Пример:
Входные данные:
5 // Количество троек
// Сами значения
2 3 2
2 3 3
2 2 1
3 3 5
1 1 1

Выходные данные:
10

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

Да, для понимание условие довольно сложное, но исходя из того примера, что я привел выше, мы должны сложить числа 2, 2, 2, 3, 1. Третьей цифрой по идеи должна быть единица, но поскольку 2+ 2 + 1 + 3 + 1 = 9 (нечетное), то мы вынуждены использовать двойку вместо единицы.
0
-1 / 25 / 4
Регистрация: 27.11.2017
Сообщений: 375
28.05.2018, 09:32 4
Неправильная стратегия. Может получиться так, что выбрав все минимальные элементы из каждой тройки, в конечном счете, когда встанет необходимость замены одного числа другим, у Вас просто не найдется числа нужной четности.
Так что Ваш алгоритм будет ломаться на некоторых наборах.

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

И кроме того, не любые наборы позволяют решить данную задачу. Подумайте сами, при каких наборах решение данной задачи невозможно.
0
IT_Exp
Эксперт
87844 / 49110 / 22898
Регистрация: 17.06.2006
Сообщений: 92,604
28.05.2018, 09:32

Заказываю контрольные, курсовые, дипломные и любые другие студенческие работы здесь.

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

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

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

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


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

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

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