1

Лайнландия представляет из себя одномерный мир, являющийся прямой, на котором распологаются N городов, последовательно пронумерованных от 0 до N - 1 . Направление в сторону от первого города к нулевому названо западным, а в обратную "— восточным.

Когда в Лайнландии неожиданно начался кризис, все были жители мира стали испытывать глубокое смятение. По всей Лайнландии стали ходить слухи, что на востоке живётся лучше, чем на западе.

Так и началось Великое Лайнландское переселение. Обитатели мира целыми городами отправились на восток, покинув родные улицы, и двигались до тех пор, пока не приходили в город, в котором средняя цена проживания была меньше, чем в родном.

Входные данные В первой строке дано одно число N ( 2 ≤ N ≤ 10 5 ) "— количество городов в Лайнландии. Во второй строке дано N чисел a i ( 0 ≤ a i ≤ 10 9 ) "— средняя цена проживания в городах с нулевого по ( N - 1) -ый соответственно.

Выходные данные Для каждого города в порядке с нулевого по ( N - 1) -ый выведите номер города, в который переселятся его изначальные жители. Если жители города не остановятся в каком-либо другом городе, отправившись в Восточное Бесконечное Ничто, выведите - 1 . входные данные

10
1 2 3 2 1 4 2 5 3 1

выходные данные

-1 4 3 4 -1 6 9 8 9 -1 

мой код:

#include <iostream>
#include <stdio.h>
#include <stdlib.h>
#include <cmath>
#include <vector>
using namespace std;

int main()
{
    int n;
    cin >> n;
    vector<int> s(n);
    vector<int> res(n);
    for(int i =0; i<n;i++)
    {
        cin>> s[i];
    }
    int r = 0;

    for(int i =0; i<n;i++)
    {

        for(int k = i; k<n;k++)
        {
            if(s[k]<s[i])
            {
                res.push_back(k);
                r = 1;

                break;
            }

        }
        if(r==0)
        {
            res.push_back(-1);
        }
        else{
            r = 0;
        }
    }
    for(int i =0; i<n; i++)
    {
        cout << res[i] << " ";
    }

}

Ввожу числа, но выводит res выводит нули.

1 ответ 1

3

Вы изначально для создания результирующего вектора res используете конструктор, размещающий в векторе n-элементов со значениями по умолчанию (для int это нули).

vector<int> res(n);

Далее в конец контейнера функцией push_back добавляются новые значения, а выводятся на печать только первые n, которые и содержат нули.

Создавайте пустой результирующий вектор и зарезервируйте память для последующих вставок, которые вы осуществляете в ходе работы программы:

std::vector<int> res;
res.reserve(n);

Для вывода результата стоит ориентироваться не на переменную n, а на фактический размер вектора:

for(size_t idx = 0; idx < res.size(); ++idx)
{
    std::cout << res[idx] << " ";
}

Либо обязательно проверяйте, что индекс элемента, к которому вы обращаетесь, валиден и не выходит за границы вектора idx < res.size().

1
  • 1
    ну и просто уточню. при размере 10^5 это будет работать достаточно долго. нужно придумать другой алгоритм.
    – pavel
    Commented 26 нояб. 2019 в 10:18

Ваш ответ

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

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