13 / 13 / 9
Регистрация: 28.07.2017
Сообщений: 103
1

Подсчеты в строю - оптимальный алгоритм

13.04.2018, 23:03. Показов 1410. Ответов 1
Метки нет (Все метки)

Author24 — интернет-сервис помощи студентам
Здравствуйте. Есть задача. Условие следующее:

Кликните здесь для просмотра всего текста

Так, например, если в шеренге стоят 4 солдата ростом https://www.cyberforum.ru/cgi-bin/latex.cgi?{h}_{1} = 178, https://www.cyberforum.ru/cgi-bin/latex.cgi?{h}_{2} = 180, https://www.cyberforum.ru/cgi-bin/latex.cgi?{h}_{3} = 170, https://www.cyberforum.ru/cgi-bin/latex.cgi?{h}_{4} =

190, а также все солдаты смотрят влево, то 2-й солдат будет видеть только 1-го, 3-й — только 2-го (так как между ним и первым есть более высокий второй солдат), 4-й будет

видеть 2-го и 3-го солдат.
Так как делать в строю все равно больше нечего, Вася хочет посчитать, сколько человек видит
каждый из солдат.

Формат входных данных:
Первая строка входных данных содержит число n — количество солдат в шеренге (1 https://www.cyberforum.ru/cgi-bin/latex.cgi?{\ll }_{} n https://www.cyberforum.ru/cgi-bin/latex.cgi?{\ll }_{} https://www.cyberforum.ru/cgi-bin/latex.cgi?{10}^{5}).

Вторая строка содержит n чисел https://www.cyberforum.ru/cgi-bin/latex.cgi?{h}_{1}, https://www.cyberforum.ru/cgi-bin/latex.cgi?{h}_{2},..., https://www.cyberforum.ru/cgi-bin/latex.cgi?{h}_{n} — рост солдат в шеренге (1 https://www.cyberforum.ru/cgi-bin/latex.cgi?{\ll }_{} n https://www.cyberforum.ru/cgi-bin/latex.cgi?{\ll <br />
<br />
}_{} https://www.cyberforum.ru/cgi-bin/latex.cgi?{10}^{5}).

Третья строка содержит n символов, описывающих направление, в которые смотрят солдаты:
i-й символ равен «L», если i-й солдат смотрит влево, то есть потенциально может увидеть только солдат с номерами 1, 2,..., i - 1, либо «R», если i-й солдат смотрит вправо и потенциально может увидеть только солдат с номерами i + 1, i + 2,..., n.

Формат выходных данных:
Выведите n целых чисел, i-е из выведенных чисел должно быть равно числу солдат, которых видит i-й солдат в строю.


Пример:
Кликните здесь для просмотра всего текста

Ввод:
4
178 180 170 190
LLLL
Вывод:
0 1 1 2

Ввод:
5
178 180 175 170 190
LLRLL
Вывод:
0 1 2 2 3

Ввод:
5
178 180 170 170 160
LLRLL
Вывод:
0 1 1 2 3


Алгоритм полным перебором слишком долгий. По веремени он не проходит.
Вот его реализация:
Кликните здесь для просмотра всего текста

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
58
59
#include <iostream>
#include <cstdio>
#include <string>
 
void fill_all (int *arr, const int &qSolders, std::string &str)
{
    for (int ind = 0; ind < qSolders; ++ind)
    {
        scanf ("%d", &arr[ind]);
    }
    std::cin >> str;
}
 
void calc (int *arr, const int &qSolders, const std::string &str)
{
    for (int ind = 0; ind < qSolders; ++ind)
    {
        int counter = 0;
        if (str[ind] == 'L')
        {
            int bH = 0;
            for (int subInd = ind - 1; subInd >= 0; --subInd)
            {
                if (arr[subInd] >= bH)
                {
                    ++counter;
                    bH = arr[subInd];
                }
            }
        }
        else
        {
            int bH = 0;
            for (int subInd = ind + 1; subInd < qSolders; ++subInd)
            {
                if (arr[subInd] >= bH)
                {
                    ++counter;
                    bH = arr[subInd];
                }
            }
        }
        printf ("%d ", counter);
    }
    printf ("\n");
}
 
int main ()
{
    int qSolders;
    std::cin >> qSolders;
 
    int *arr = new int [qSolders];
    std::string str;
    fill_all (arr, qSolders, str);
    calc (arr, qSolders, str);
 
    return 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
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
#include <iostream>
#include <cstdio>
#include <string>
 
////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
void fill_all (int *arr, int *ans, const int &qSolders, std::string &str);
void calc (int *arr, int *ans, const int &qSolders, const std::string &str);
void cycle (int *arr, int *ans, const std::string &str, const int &qSolders, int &index, const int &ind, int &bh, char ch);
void printOut (int *ans, const int &size);
template <typename T> T abs (T num);
 
////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
int main ()
{
    int qSolders;
    std::cin >> qSolders;
 
    int *arr = new int [qSolders];
    int *ans = new int [qSolders];
    std::string str;
    fill_all (arr, ans, qSolders, str);
    calc (arr, ans, qSolders, str);
    printOut (ans, qSolders);
 
    return 0;
}
 
////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
void fill_all (int *arr, int *ans, const int &qSolders, std::string &str)
{
    for (int ind = 0; ind < qSolders; ++ind)
    {
        scanf ("%d", &arr[ind]);
        ans[ind] = 0;
    }
    std::cin >> str;
}
 
////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
void calc (int *arr, int *ans, const int &qSolders, const std::string &str)
{
    //////////////////////////////////
    ///Left
    int bh = 0;
    int index = 0;
    for (int ind = 0; ind < qSolders; ++ind)
    {
        cycle (arr, ans, str, qSolders, index, ind, bh, 'R');
    }
 
    //////////////////////////////////
    ///Right
    bh = 0;
    index = qSolders - 1;
    for (int ind = qSolders - 1; ind >= 0; --ind)
    {
        cycle (arr, ans, str, qSolders, index, ind, bh, 'L');
    }
}
 
////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
void cycle (int *arr, int *ans, const std::string &str, const int &qSolders, int &index, const int &ind, int &bh, char ch)
{
    //////////////////////////////////
    if (str[ind] != ch)
    {
        ans[ind] = abs(ind - index);
    }
 
    //////////////////////////////////
    if (arr[ind] >= bh)
    {
        bh = arr[ind];
        index = ind;
    }
}
 
////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
void printOut (int *ans, const int &size)
{
    for (int ind = 0; ind < size; ++ind)
    {
        printf ("%d ", ans[ind]);
    }
    printf ("\n");
}
 
////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
template <typename T>
T abs (T num)
{
    return num < 0 ? -num : num;
}


При таком алгоритме ход "мышления" такой: сначала преребираем всех солдат, которые смотрят в одну сторону, затем, в другую.
Перебирая каждую сторону мы запоминаем индекс самого большого солдата (т.е. того, после которого мы ничего не сможем увидеть).
Например, у нас есть солдаты в таком порядке 1 2 3 4 99 98 97.
Солдат номер 1, смотрящий направо будет видеть всех солдат до тех пор, пока не увидит солдата с высотой 99.

И вот тут, если немного изменить порядок, алгоритм уже работает неправильно. К примеру, на такой: 1 2 4 3 99 98 97.
Алгоритм вычислит тот же ответ, что и в предыдущем примере, однако солдат 1 не сможет увидеть солдата с высотой 3, т.к. предыдущий солдат выше, чем 3.

Подскажите, пожалуйста, каким образом можно решить данную задачу.
Заранее, спассибо (:
0
Programming
Эксперт
94731 / 64177 / 26122
Регистрация: 12.04.2006
Сообщений: 116,782
13.04.2018, 23:03
Ответы с готовыми решениями:

оптимальный алгоритм
найти сумму простых чисел от 1 до A program kl; var s,m,p,n,A:integer; begin read (A); for...

Оптимальный алгоритм сортировки
Камрады! Есть функция/процедура f(m,n), которая получает 2 номера и возвращает n,m (n&gt;m) т.е....

Оптимальный алгоритм сортировки
Доброго времени суток! Есть некий класс: public class Person { public string Name {...

Оптимальный алгоритм амплитудного демодулятора
Доброго времени суток. Возникла задача - детектирование АМ сигнала с синусоидальной несущей в 4...

1
13 / 13 / 9
Регистрация: 28.07.2017
Сообщений: 103
16.04.2018, 10:09  [ТС] 2
Модификация алгоритма полного перебора. Теперь мы не перебираем все по новой, а идем от текущего солдата до самого длинного, проверяя каждого на пути. Смысла идти и проверять дальше самого высокого солдата смысла нету - за ним и так ничего видно не будет. Но алгоритм до сих пор работает медленно.

Вот его реализация:
Кликните здесь для просмотра всего текста
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
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
#include <iostream>
#include <cstdio>
#include <string>
 
void fill_all (int *arr, int *ans, const int &qSolders, std::string &str)
{
    for (int ind = 0; ind < qSolders; ++ind)
    {
        scanf ("%d", &arr[ind]);
        ans[ind] = 0;
    }
    std::cin >> str;
}
 
void calc (int *arr, int *ans, const int &qSolders, const std::string &str)
{
    //left
    int bh = 0, index = 0;
    for (int ind = 0; ind < qSolders; ++ind)
    {
        if (str[ind] == 'L')
        {
            int counter = 0;
            int tempBH = 0;
            int tempIndex = ind - 1;
            for (int J = ind - 1; J >= index; --J)
            {
                if (arr[J] >= tempBH)
                {
                    ++counter;
                    tempBH = arr[J];
                    tempIndex = J;
                }
            }
            ans[ind] = counter;
        }
 
        if (arr[ind] > bh)
        {
            bh = arr[ind];
            index = ind;
        }
    }
 
    //right
    bh = 0, index = qSolders - 1;
    for (int ind = qSolders - 1; ind >= 0; --ind)
    {
        if (str[ind] == 'R')
        {
            int counter = 0;
            int tempBH = 0;
            int tempIndex = ind + 1;
            for (int J = ind + 1; J <= index; ++J)
            {
                if (arr[J] >= tempBH)
                {
                    ++counter;
                    tempBH = arr[J];
                    tempIndex = J;
                }
            }
            ans[ind] = counter;
        }
 
        if (arr[ind] > bh)
        {
            bh = arr[ind];
            index = ind;
        }
    }
}
 
int main ()
{
    int qSolders;
    std::cin >> qSolders;
 
    int *arr = new int [qSolders];
    int *ans = new int [qSolders];
    std::string str;
    fill_all (arr, ans, qSolders, str);
    calc (arr, ans, qSolders, str);
 
    for (int i = 0; i < qSolders; ++i)
    {
        printf ("%d ", ans[i]);
    }
    printf ("\n");
 
    return 0;
}


Добавлено через 11 часов 16 минут
Еще одно улучшение. Тест, на котором был превышен лимит времени уже прошел успешно, но тесты дальше все-равно по времени не проходят. Код:

Кликните здесь для просмотра всего текста
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
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
#include <iostream>
#include <cstdio>
#include <string>
 
void fill_all (int *arr, int *ans, const int &qSolders, std::string &str)
{
    for (int ind = 0; ind < qSolders; ++ind)
    {
        scanf ("%d", &arr[ind]);
        ans[ind] = 0;
    }
    std::cin >> str;
}
 
void calc (int *arr, int *ans, const int &qSolders, const std::string &str)
{
    //left
    int bh = 0, index = 0;
    for (int ind = 0; ind < qSolders; ++ind)
    {
        if (str[ind] == 'L')
        {
            if (ind - 2 >= 0 && str[ind - 1] == 'L' && arr[ind - 1] <= arr[ind - 2])
            {
                ans [ind] = ans[ind - 1] + 1;
            }
            else
            {
                int counter = 0;
                int tempBH = 0;
                int tempIndex = ind - 1;
                for (int J = ind - 1; J >= index; --J)
                {
                    if (arr[J] >= tempBH)
                    {
                        ++counter;
                        tempBH = arr[J];
                        tempIndex = J;
                    }
                }
                ans[ind] = counter;
            }
        }
 
        if (arr[ind] > bh)
        {
            bh = arr[ind];
            index = ind;
        }
    }
 
    //right
    bh = 0, index = qSolders - 1;
    for (int ind = qSolders - 1; ind >= 0; --ind)
    {
        if (str[ind] == 'R')
        {
            if (ind + 2 <= qSolders - 1 && str[ind + 1] == 'R' && arr[ind + 1] <= arr[ind + 2])
            {
                ans[ind] = ans[ind + 1] + 1;
            }
            else
            {
                int counter = 0;
                int tempBH = 0;
                int tempIndex = ind + 1;
                for (int J = ind + 1; J <= index; ++J)
                {
                    if (arr[J] >= tempBH)
                    {
                        ++counter;
                        tempBH = arr[J];
                        tempIndex = J;
                    }
                }
                ans[ind] = counter;
            }
        }
 
        if (arr[ind] > bh)
        {
            bh = arr[ind];
            index = ind;
        }
    }
}
 
int main ()
{
    int qSolders;
    std::cin >> qSolders;
 
    int *arr = new int [qSolders];
    int *ans = new int [qSolders];
    std::string str;
    fill_all (arr, ans, qSolders, str);
    calc (arr, ans, qSolders, str);
 
    for (int i = 0; i < qSolders; ++i)
    {
        printf ("%d ", ans[i]);
    }
    printf ("\n");
 
    return 0;
}
0
16.04.2018, 10:09
IT_Exp
Эксперт
87844 / 49110 / 22898
Регистрация: 17.06.2006
Сообщений: 92,604
16.04.2018, 10:09
Помогаю со студенческими работами здесь

Перемножение матриц. Оптимальный алгоритм
Доброе время суток! Объясните пожалуйста почему такой алгоритм перемножения матриц: for (int i...

Оптимальный алгоритм рисования линий
1) Является ли алгоритм рисования линии перебором точек оптимальным? for(float i=Xmin, j; i&lt;=Xmax;...

Перебор цифр и оптимальный алгоритм
Всем, добрый день. Есть набор цифр от 1 до 5. В числе может быть от 1 до 15 цифр. Например,...

Помогите написать оптимальный алгоритм по рисунку
Нужна ваша помощь, помогите написать оптимальный алгоритм по рисунку. Это мой код: uses ...


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

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

КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin
Copyright ©2000 - 2024, CyberForum.ru