C/C++

Можете пожалуйста решить ещё задачу на с++. Письменно алгоритмом или код на с++.

Вам дан массив a1,a2,…,an целых чисел (положительных, отрицательных или 0 ). Вы можете выполнить над массивом несколько операций (возможно, 0 ). Операция производится так: выбираются i,j (1≤i,j≤n , они могут быть равны) и задается ai:=ai+aj (т.е. к ai прибавляется aj ). Сделайте массив неубывающим (т.е. ai≤ai+1 для 1≤i≤n−1 ) не более чем за 50 операций. Минимизировать количество операций не требуется. Входные данные Каждый тест состоит из нескольких наборов входных данных. В первой строке находится одно целое число t (1≤t≤500 ) — количество наборов входных данных. Далее следует описание наборов входных данных. Первая строка каждого набора содержит одно целое число n (1≤n≤20 ) — длину массива. Вторая строка содержит n целых чисел a1,a2,…,an (−20≤ai≤20 ) — массив перед выполнением операций. Выходные данные Для каждого набора входных данных выведите свои операции в следующем формате: Первая строка должна содержать целое число k (0≤k≤50 ) — количество операций. Следующие k строк представляют собой k операций по порядку. Каждая из этих k строк должна содержать два целых числа i и j (1≤i,j≤n ) — соответствующая операция заключается в прибавлении aj к ai . После всех операций массив a1,a2,…,an должен быть неубывающим.
входные данные
10
2
2 1
4
1 2 -10 3
5
2 1 1 1 1
8
0 0 0 0 0 0 0 0
5
1 2 -4 3 -10
10
11 12 13 14 15 -15 -16 -17 -18 -19
7
1 9 3 -4 -3 -2 -1
3
10 9 8
20
1 -14 2 -10 6 -5 10 -13 10 7 -14 19 -5 19 1 18 -16 -7 12 8
20
-15 -17 -13 8 14 -13 10 -4 11 -4 -16 -6 15 -4 -2 7 -9 5 -5 17
выходные данные
1
2 1
3
4 4
4 4
3 4
4
2 1
3 1
4 1
5 1
0
7
3 4
3 4
5 4
5 4
5 4
5 4
5 4
15
6 1
6 1
6 1
7 2
7 2
7 2
8 3
8 3
8 3
9 4
9 4
9 4
10 5
10 5
10 5
8
3 4
3 4
2 4
2 4
2 4
2 4
1 4
1 4
3
2 1
3 1
3 1
31
14 1
18 7
13 11
15 11
6 4
5 17
19 6
19 12
10 5
11 12
1 17
15 19
16 10
14 2
16 11
20 7
7 6
9 5
3 6
6 14
17 18
18 14
12 3
17 16
8 18
13 16
9 8
14 8
16 2
11 8
12 7
31
5 12
19 13
9 1
5 17
18 19
6 16
15 8
6 9
15 14
7 10
19 7
17 20
14 4
15 20
4 3
1 8
16 12
16 15
5 6
12 10
11 15
20 3
20 19
13 14
11 14
18 10
7 3
12 17
4 7
13 2
11 13
Примечание В первом наборе входных данных, добавив к a2 a1=2 , получим массив [2,3] , который является неубывающим. Во втором наборе входных данных массив изменяется следующим образом: [1,2,−10,3] [1,2,−10,6] [1,2,−10,12] [1,2,2,12] В третьем наборе входных данных итоговый массив имеет вид [2,3,3,3,3]
Александр Веревкин
Александр Веревкин
455
Понятно сформулированный вопрос,
это 90% ответа.
Я ничего не понял.
Идите на киберфорум ру
Евгений Даломанов
Евгений Даломанов
75 398
Лучший ответ
Альберт Халиуллин это с кодфорсес задача
Вам нужно написать программу, которая решает задачу о неубывающем массиве. Для этого, можно выбрать простой подход - каждый раз, когда мы сталкиваемся с числом, которое меньше предыдущего, мы можем прибавить к нему предыдущее число. Это гарантированно сделает массив неубывающим, так как каждый следующий элемент будет хотя бы таким же, как предыдущий.

Вот пример реализации этого подхода на C++:

```cpp
#include<bits/stdc++.h>
using namespace std;

int main() {
ios::sync_with_stdio(false);
cin.tie(0);
int t;
cin >> t;
while (t--) {
int n;
cin >> n;
vector<int> a(n);
for (int& x : a) cin >> x;
vector<pair<int, int>> ops;
for (int i = 1; i < n; ++i) {
if (a[i] < a[i - 1]) {
ops.push_back({i + 1, i});
a[i] += a[i - 1];
}
}
cout << ops.size() << "\n";
for (auto& op : ops) {
cout << op.second << " " << op.first << "\n";
}
}
return 0;
}
```
В этом коде мы сначала считываем количество тестовых случаев. Для каждого теста, мы считываем размер массива и его элементы. Затем мы проходим по каждой паре последовательных элементов в массиве. Если следующий элемент меньше текущего, то мы добавляем разницу между текущим и следующим элементами к следующему элементу и сохраняем пару индексов как операцию. После того как все операции были выполнены, мы выводим их количество и сами операции.

Обратите внимание, что операции индексации в C++ начинаются с 0, в то время как в вашем задании они начинаются с 1, поэтому в выводе я добавляю 1 к каждому индексу.
Денис Хоботов
Денис Хоботов
14 368
Эльчин Алиев
можем прибавить к нему предыдущее число. Это гарантированно сделает массив неубывающим

Это так только для неотрицательных чисел:
 aᵢ ≤ aᵢ₊₁ + aᵢ ⇒ aᵢ₊₁ ≥ 0
А по условию числа могут быть и отрицательными.

Похожие вопросы