Chúng ta được cung cấp một mảng đích arr [] chứa các số nguyên dương. Mục đích là để xây dựng mảng đích arr [] bằng cách sử dụng một mảng ban đầu có tất cả các số 0. Các phép toán có thể được áp dụng trên một mảng trống nhất định với tất cả các số 0 sẽ mang hậu tố là các phép toán tăng / giảm.
Nếu chúng ta chọn bất kỳ chỉ mục nào có nghĩa là i, thì trong trường hợp hoạt động gia tăng hậu tố, chúng ta sẽ thêm 1 vào tất cả các phần tử từ chỉ mục i cho đến chỉ mục cuối cùng.
Trong trường hợp hoạt động giảm dần hậu tố, chúng tôi sẽ trừ 1 cho tất cả các phần tử từ chỉ mục i cho đến chỉ mục cuối cùng.
Hãy cho chúng tôi hiểu với các ví dụ
Đầu vào - arr [] ={1,2,3}
Đầu ra - Số lượng các phép toán tăng / giảm hậu tố để tạo một mảng nhất định là - 3
Giải thích
Starting from { 0, 0, 0 }
Choose index 0, applying suffix increment { 1, 1, 1 }
Choose index 1, applying suffix increment { 1, 2, 2 }
Choose index 2, applying suffix increment { 1, 2, 3 }
Total operations =3 Đầu vào - arr [] ={1, 4, 5, 3}
Đầu ra - Số lượng các phép toán tăng / giảm hậu tố để tạo một mảng nhất định là - 7
Giải thích
Starting from { 0, 0, 0, 0 }
Choose index 0, applying suffix increment { 1, 1, 1, 1 }
Choose index 1, applying suffix increment { 1, 2, 2, 2 }
Choose index 1, applying suffix increment { 1, 3, 3, 3 }
Choose index 1, applying suffix increment { 1, 4, 4, 4 }
Choose index 2, applying suffix increment { 1, 4, 5, 5 }
Choose index 3, applying suffix decrement { 1, 4, 5, 4 }
Choose index 3, applying suffix decrement { 1, 4, 5, 3 }
Total operations = 7 Phương pháp tiếp cận được sử dụng trong chương trình dưới đây như sau
Nếu chúng ta lấy mảng ban đầu là B []. Để làm cho phần tử đầu tiên B [0] bằng arr [0]. Chúng ta sẽ cần arr [0] số phép toán tăng hậu tố. Sau đó, tất cả B [0] =B [1] .... =B [n-1] =arr [0] sẽ bằng nhau.
Để làm cho phần tử thứ hai B [1] bằng arr [1], chúng ta sẽ cần | arr [1] -arr [0] | số lượng hoạt động. (tăng hoặc giảm).
Vì vậy, để làm cho B [i] bằng arr [i], chúng ta sẽ cần | arr [i] - arr [i-1] | số lượng hoạt động.
Tổng số hoạt động sẽ là | arr [0] | + | arr [1] -arr [0] | +…. + | arr [n-1] -arr [n-2] |.
-
Lấy mảng mục tiêu là arr [].
-
Hàm incr_decr_op (int arr [], int size) nhận mảng và độ dài của nó và trả về số lượng các phép toán tăng / giảm hậu tố để tạo một mảng nhất định
-
Lấy số lượng ban đầu là 0.
-
Traverse array arr [] sử dụng vòng lặp for
-
Đối với chỉ số 0, hãy thêm arr [i] để đếm.
-
Đối với các chỉ mục khác, hãy thêm abs (arr [i] -arr [i-1]) để đếm.
-
Kết quả là số lượng trả về ở cuối vòng lặp for.
Ví dụ
#include <bits/stdc++.h>
using namespace std;
int incr_decr_op(int arr[], int size){
int count = 0;
for (int i = 0; i < size; i++){
if (i > 0){
count += abs(arr[i] - arr[i - 1]);
}
else{
count = count + abs(arr[i]);
}
}
return count;
}
int main(){
int arr[] = { 3, 3, 1, 2, 2 };
int size = sizeof(arr) / sizeof(arr[0]);
cout<<"Count of suffix increment/decrement operations to construct a given array are: "<<incr_decr_op(arr, size) << endl;
} Đầu ra
Nếu chúng ta chạy đoạn mã trên, nó sẽ tạo ra kết quả sau -
Count of suffix increment/decrement operations to construct a given array are: 6