Разложить книги по группам наилучшим образом

@Woubat · Регистрация: 09.04.2023

Author24 — интернет-сервис помощи студентам

В книжном магазине действует акция "Возьми 3 книги, а заплати за 2 книги". Таким образом, каждый покупатель, выбравший 3 книги, получает самую дешевую из них бесплатно. Конечно, клиент может взять еще больше книг и, в зависимости от того, как книги распределены по группам из трех, бесплатно получить самую дешевую в каждой группе.
Например, пусть цены на книги, взятые клиентом, будут следующими: 10 3 2464 9. Если он распределит их по группам: (10, 3, 2), (4, 6, 4) и (9), он получит книгу по цене 2 из первой группы и книгу по цене 4 из второй группы бесплатно. Мы видим, что из третьей группы он ничего не получит бесплатно, потому что в ней только одна книга.
У продавщицы, работающей в книжном магазине, благие намерения, и она всегда хочет макси- мально снизить стоимость покупки для каждого посетителя. При данных ценах на книги помогите ей разложить книги по группам наилучшим образом, чтобы общая стоимость, которую должен заплатить покупатель, была минимальной.
Обратите внимание: продавщице не обязательно раскладывать книги по группам, чтобы в каж- дой группе содержались ровно 3 книги, но количество книг в группе должно быть от 1 до 3 вклю-
чительно.
Формат входных данных
В первой строке вводится единственное натуральное число п (1 ≤ n≤ 105) - количество книг, которое берет покупатель.
В следующих и строчках вводится по одному натуральному числу с; (1 ≤ G≤ 105).
1-ой книги.
Формат выходных данных
- стоимость
В единственной строке выведите одно натуральное число - минимальную стоимость, которую должен заплатить покупатель.
Примеры
Стандартный ввод; Стандартный вывод:
4
3
2
3
2
8

6
6
4
5
5
5
5
21

Мой код:

C++

#include <iostream>
#include <vector>
#include <climits>
 
using namespace std;
 
int main()
{
    int n{};
    cin >> n;
 
    int cnt = n / 3;
    int cnt2 = 0;
    vector <int> arr;
    arr.resize(n);
 
    for (int i = 0; i < n; i++)
    {
        cin >> arr[i];
    }
 
    for (int i = 0; i < n; i += 3)
    {
        if (cnt2 == cnt)
            break;
        int a1, a2, a3;
        a1 = arr[i];
        a2 = arr[i + 1];
        a3 = arr[i + 2];
        int a = min(a1, min(a2, a3));
        if (a1 == a)
            arr[i] = INT_MAX;
        else if (a2 == a)
            arr[i + 1] = INT_MAX;
        else
            arr[i + 2] = INT_MAX;
        cnt2++;
    }
 
    int sum = 0;
 
    for (int i = 0; i < n; i++)
    {
        if (arr[i] != INT_MAX)
            sum += arr[i];
    }
 
    cout << sum;
 
    return 0;
}

Помогите пожалуйста, проходит только 2 теста.

@zss · 06.12.2023, 10:41

Сообщение от Woubat

быть от 1 до 3 вклю-
чительно.

Woubat, с какой целью "чительно." перенесено на отдельную строку?
Зачем в

Сообщение от Woubat

макси- мально

нужно тире?

Сообщение от Woubat

1 ≤ n≤ 105

почему 105, а не 10⁵?

@Woubat · 06.12.2023, 10:43 **[ТС]**

Просто условие задачи нельзя скопировать, через сторонние сайты с картинки в текст перевёл и не прочитал. Сейчас подправлю.

@igorrr37 · 06.12.2023, 11:10

для массива чисел тройка с максимальным профитом - это три максимальных элемента массива. Для оставшегося массива процедуру повторить.

@Woubat · 06.12.2023, 11:15 **[ТС]**

Вот актуальный, рабочий код:

C++

#include <iostream>
#include <vector>
#include <climits>
#include <algorithm>
 
using namespace std;
 
int main()
{
    int n{};
    cin >> n;
 
    int cnt = n / 3;
    int cnt2 = 0;
    vector <int> arr;
    arr.resize(n);
 
    for (int i = 0; i < n; i++)
    {
        cin >> arr[i];
    }
    
    sort(arr.begin(), arr.end());
    reverse(arr.begin(), arr.end());
 
    for (int i = 0; i < n; i += 3)
    {
        if (cnt2 == cnt)
            break;
        int a1, a2, a3;
        a1 = arr[i];
        a2 = arr[i + 1];
        a3 = arr[i + 2];
        int a = min(a1, min(a2, a3));
        if (a1 == a)
            arr[i] = INT_MAX;
        else if (a2 == a)
            arr[i + 1] = INT_MAX;
        else
            arr[i + 2] = INT_MAX;
        cnt2++;
    }
 
    int sum = 0;
 
    for (int i = 0; i < n; i++)
    {
        if (arr[i] != INT_MAX)
            sum += arr[i];
    }
 
    cout << sum;
 
    return 0;
}

@zss Модератор 13701 / 10904 / 6472 Регистрация: 18.12.2011 Сообщений: 29,108
	06.12.2023, 10:41	2
	Сообщение от Woubat быть от 1 до 3 вклю- чительно. Woubat, с какой целью "чительно." перенесено на отдельную строку? Зачем в Сообщение от Woubat макси- мально нужно тире? Сообщение от Woubat 1 ≤ n≤ 105 почему 105, а не 10⁵? 0

@Woubat 1 / 1 / 0 Регистрация: 09.04.2023 Сообщений: 61
	06.12.2023, 10:43 [ТС]	3
	Просто условие задачи нельзя скопировать, через сторонние сайты с картинки в текст перевёл и не прочитал. Сейчас подправлю. 0

@igorrr37 2857 / 2004 / 988 Регистрация: 21.12.2010 Сообщений: 3,709 Записей в блоге: 10
	06.12.2023, 11:10	4
	Сообщение было отмечено Woubat как решение Решение для массива чисел тройка с максимальным профитом - это три максимальных элемента массива. Для оставшегося массива процедуру повторить. 1

	06.12.2023, 11:15

Разложить книги по группам наилучшим образом

Решение