Форум программистов, компьютерный форум, киберфорум
С++ для начинающих
Войти
Регистрация
Восстановить пароль
 
Рейтинг 4.71/34: Рейтинг темы: голосов - 34, средняя оценка - 4.71
0 / 0 / 1
Регистрация: 18.02.2018
Сообщений: 112
1

Клиппи и Мерлин грабят банк

17.04.2018, 14:32. Показов 7035. Ответов 2
Метки нет (Все метки)

Привет всем. Решаю такую задачу:

Кликните здесь для просмотра всего текста
Клиппи и Мерлин решили грабить банк «Документы», который представляет из себя N расположенных в ряд банковских ячеек, пронумерованных последовательно числами от 1 до N .

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

Чтобы не вызывать лишних подозрений, Клиппи и Мерлин решили ограбить всего две ячейки "— по одной на каждого. Также, чтобы охрана банка не почуяла неладного, они решили работать далеко друг от друга "— между ними должно быть не меньше K банковских ячеек.

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

Выходные данные
Выведите два числа в возрастающем порядке "— номера ячеек, которые нужно ограбить, чтобы суммарно украсть как можно более дорогие ценности, не вызвав при этом лишних подозрений. Если вариантов несколько выберите тот, в котором меньший номер вскрываемой ячейки был как можно ближе к единице, чтобы в экстренном случае покинуть банк как можно скорее. Если и таких вариантов несколько, выберите тот, в котором и больший номер вскрываемой ячейки был как можно меньше.


Я написал вот такую программу:

C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
#include <iostream>
#include <algorithm>
using namespace std;
int main() {
    int n, k, lol = 1, lol2;
    cin >> n >> k;
    lol2 = k + 2;
    int*a = new int[n];
    for (int i = 0; i < n; i++) cin >> a[i];
    int64_t ma = a[0] + a[k + 1];
    for (int i = 1; i < n; i++) {
        for (int j = i + k + 1; j < n; j++) {
            if (a[i] + a[j] > ma) {
                ma = a[i] + a[j];
                lol = i + 1;
                lol2 = j + 1;
            }
        }
    }
    cout << lol << ' ' << lol2;
 
}
Мой код не проходит 3 теста(проходит 14 тестов из 17), пишет превышено время. Помогите мне сократить время выполнения моей задачи.
0

Помощь в написании контрольных, курсовых и дипломных работ здесь.

Programming
Эксперт
94731 / 64177 / 26122
Регистрация: 12.04.2006
Сообщений: 116,782
17.04.2018, 14:32
Ответы с готовыми решениями:

Грабят объявления с сайта!
Установил на сайт с объявлениями скрипт записывающий GET-запросы юзеров, дабы мониторить хакерские...

С сайта грабят контент - не обращать внимание?
В сайт встроил скрипт, отслеживающий GET-запросы. Постоянно, в логах скрипта, приходится видеть...

Банк
Банк предлагвет 3 вида срочных вкладов: на 3 месяца под p1%,на 6 месяцев под p2% и на год под...

Банк
print('Добро пожаловать в интернет-банк!') print('У нас фантастические процентные ставки!')...

2
1 / 1 / 0
Регистрация: 28.03.2019
Сообщений: 4
03.07.2019, 09:54 2
Это задача на линейный алгоритм тебе нужно придумать решение чтобы не записывать числа в массив поэтому асимптотика памяти станет O(n) вместо О(n2)
1
6 / 10 / 2
Регистрация: 08.08.2019
Сообщений: 63
12.08.2019, 10:32 3
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
#include <iostream>
using namespace std;
const int N=1E5;
int a[N], p[N], s[N];
 
int main() {
int n, k, i, j;
cin >> n >> k;
for (i=0, j=0; i<n; i++) {
cin >> a[i];
if (a[i] > a[j]) {p[i] = i; j = i;} else p[i] = p[j];
}
for (i=n-1, j=n-1; i>=0; i--) {
if (a[i] >= a[j]) {s[i] = i; j = i;} else s[i] = s[j];
}
int f = 0, l = 0, r = k+1;
for (i=l, j=r; j<n; i++, j++) {
int t = a[p[i]] + a[s[j]];
if (t > f) {l = p[i]; r = s[j]; f = t;}
}
cout << (l+1) << " " << (r+1);
}
Отметьте, если помог
2
IT_Exp
Эксперт
87844 / 49110 / 22898
Регистрация: 17.06.2006
Сообщений: 92,604
12.08.2019, 10:32

Помощь в написании контрольных, курсовых и дипломных работ здесь.

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

Банк памяти
Добрый день! Задали вопрос: Что такое банк памяти? (Тема: Оперативная память. ОЗУ, RAM). Искал в...

Альфа-Банк:
Посмотрел что в альфа-банке самые выгодные условия обналички. Пришел, тычу им чек, они пытаются...

Клиент-банк
Всем добрый день! Постоянно слышу про &quot;написать обработку клиент-банк&quot;, но ни разу не делала, а...


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

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

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