2

Даны n целых чисел и ряд из n коробок. Между коробками фиксировано расположены знаки неравенств. Разработайте программу, которая "помещает" числа в коробки так, чтобы неравенства были правильные.

Например, числа: 2 5 1 0. Знаки: < > <. Решение: 0<5>1<2.

Есть наработки, но всё плохо.

#include <iostream>
#include <vector>
#include <string>
#include <algorithm>
using namespace std;

int main()
{
    string s1, s2;
    getline(cin, s1);
    getline(cin, s2);
    sort(s1.begin(), s1.end());

    int cur1 = 0, cur2 = 0, cur = 0;
    int kolright = 0, countright = 0;

    vector<int>rez(s1.size());
    for (int i = 0; i < s2.size(); i++)
    {
        if (s2[i] == '<')
        {
            rez[cur] = s1[cur1];
            cur1++;
            cur2++;
            i++;
        }
        else
        {
            while (s2[i] == '>')
            {
                kolright++;
                i++;
            }
            for (int j = 0; j <= kolright; j++)
                rez[cur2 + j] = s1[cur1 + kolright - j];
            cur2 += kolright; cur2++;
            cur1 += countright; cur1++;
            kolright = 0;
        }
    }
    for (int k = 0; k < rez.size(); k++)
        cout << rez[k] << " ";
    return 0;
}
14
  • Не парься, для зачёта хватит и полного перебора.
    – Akina
    29 мая 2019 в 9:09
  • @Akina А если коробок - штук 100?... :)
    – Harry
    29 мая 2019 в 9:11
  • 2
    @Harry Ну будет долго работать, и что? Ну получит зачёт в следующем году, когда программа отработает, делов-то...
    – Akina
    29 мая 2019 в 9:13
  • Напишите что именно не так с этим кодом. 29 мая 2019 в 9:34
  • @Akina Вы оцениваете полный перебор 100! годом?... 8-/
    – Harry
    29 мая 2019 в 9:35

1 ответ 1

1

Даём каждой коробке уровень. Начинаем с самой левой. Её уровень 0 (можно n - 1, для удобства) . Если < уровень следующей коробки + 1 от текущей, если > уровень -1. Это делается за линию. Потом выдаём номера. Начинаем с самого большого уровня и выбираем самые большие из оставшихся. Если во время шага 1 завести массив уровней (всего может быть 2n-1 уровней), в котором хранить какие коробки на этом уровне, то тоже работает за линию.

2
  • 1
    Единственное, в случае возможности одинаковых входных чисел — нужно определиться с критерием невозможности решения. Простейший пример: 1 > 1 . Ну и нет, не за линию. Формулировки вроде "самые большие из оставшихся" подразумевают сортировку.
    – vp_arth
    29 мая 2019 в 10:26
  • 1
    Да, ещё нужна сортировка n*log(n). Я думал числа по порядку идут. И если числа могут быть одинаковыми, это решение не работает. 29 мая 2019 в 12:42

Ваш ответ

Нажимая на кнопку «Отправить ответ», вы соглашаетесь с нашими условиями использования и подтверждаете, что прочитали и поняли наши политику конфиденциальности и нормы поведения.

Всё ещё ищете ответ? Посмотрите другие вопросы с метками или задайте свой вопрос.