Top.Mail.Ru
Ответы

Помогите найти ошибку

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

Входные данные
В первой строке вводятся два числа — N ( 2 ⩽N⩽ 105) и K (0 ⩽K<N− 1) соответственно. В второй строке вводятся N чисел ai(0 ⩽ai⩽ 109) — стоимости хранимых ценностей в ячейках от 1 до N соответственно.

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

Примеры
Ввод
6 2
2 4 3 1 4 4
Вывод
2 5

123456789101112131415161718192021222324252627282930
 #include <iostream> 
#include <vector> 
using namespace std; 
 
int main() 
{ 
	int n, k; cin >> n >> k; 
	vector <int> a(n); 
 
	for (int i = 0; i < n; ++i) 
		cin >> a[i]; 
 
	int ibest = 0; 
	int jbest = k + 1; 
	int imax = 0; 
 
	for (int j = k + 2; j < n; ++j) 
	{ 
		if (a[j - (k + 1)] > a[imax]) 
			imax = j - (k + 1); 
		if (a[j] > a[jbest]) 
			jbest = j; 
		if (a[imax] > a[ibest]) 
			ibest = imax; 
	} 
 
	cout << ibest + 1 << " " << jbest + 1; 
 
	return 0; 
} 

Помогите найти ошибку

По дате
По рейтингу
Аватар пользователя
Ученик
10мес

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

1
 Call.Polizeinen("Achtung!! Hende Hoch!"); 
Аватар пользователя
Мастер
10мес

Вот такой тест:
6 2
3 7 2 4 0 1
Вывод: 2 4. Правильный вывод: 2 6.
Если выполнился первый if, то это не значит, что в этой же итерации выполнится второй if. Таким образом, нарушается расстояние k.
Решение, я как понял, не нужно?

Аватар пользователя
Мудрец
10мес
123456789101112131415161718192021222324252627282930313233343536
 #include <bits/stdc++.h> 
using namespace std; 
 
int main() { 
    ios::sync_with_stdio(false); 
    cin.tie(nullptr); 
 
    int N, K; 
    if (!(cin >> N >> K)) return 0; 
    vector<long long> a(N); 
    for (int i = 0; i < N; ++i) cin >> a[i]; 
 
    // текущий индекс с максимальным a[i] среди i <= j-K-1 
    int max_i = 0; 
 
    // рекордная пара 
    int best_i = 0, best_j = K + 1; 
    long long best_sum = a[best_i] + a[best_j]; 
 
    for (int j = K + 1; j < N; ++j) { 
        int cand = j - K - 1;              // последний индекс, который можно ставить слева от j 
        if (cand >= 0 && a[cand] > a[max_i]) max_i = cand; 
 
        long long cur_sum = a[max_i] + a[j]; 
        if (cur_sum > best_sum || 
            (cur_sum == best_sum && 
             (max_i < best_i || (max_i == best_i && j < best_j)))) { 
            best_sum = cur_sum; 
            best_i = max_i; 
            best_j = j; 
        } 
    } 
 
    cout << best_i + 1 << ' ' << best_j + 1 << '\n'; 
    return 0; 
} 
Аватар пользователя
Мыслитель
10мес

Да, тут охренеть как нужен long long, а смысл этого условия ты и сам не скажешь, чатгптшный король школьных домашек:

1
 (max_i < best_i || (max_i == best_i && j < best_j)) 

Не скажешь, потому что сам не знаешь, что делает вся эта портянка кода, найденная твоим чатгпт на неведомой индусской помойке...

Аватар пользователя
Ученик
10мес

Спасибо конечно, но я просил найти ошибки в моём коде, смысл того что я спишу у вас = 0, некоторые вещи я вообще впервые вижу



Видео по теме