Đếm số phép toán hậu tố tăng/giảm để xây dựng mảng mục tiêu trong C++

Cho một mảng mục tiêu arr[] chứa các số nguyên dương. Mục tiêu là xây dựng mảng mục tiêu từ mảng ban đầu toàn 0. Các phép toán cho phép trên mảng rỗng toàn 0 là phép toán hậu tố tăng/giảm (suffix increment/decrement).

Nếu chọn chỉ số i, trường hợp tăng hậu tố: cộng 1 vào tất cả phần tử từ chỉ số i đến cuối.

Trường hợp giảm hậu tố: trừ 1 từ tất cả phần tử từ chỉ số i đến cuối.

Ví dụ

Đầu vào - arr[] = {1, 2, 3}

Đầu ra - Số phép toán hậu tố tăng/giảm là 3

Giải thích

Bắt đầu {0, 0, 0}
Chọn chỉ số 0, tăng hậu tố -> {1, 1, 1}
Chọn chỉ số 1, tăng hậu tố -> {1, 2, 2}
Chọn chỉ số 2, tăng hậu tố -> {1, 2, 3}
Tổng phép toán = 3

Đầu vào - arr[] = {1, 4, 5, 3}

Đầu ra - Số phép toán hậu tố tăng/giảm là 7

Giải thích

Bắt đầu {0, 0, 0, 0}
Chỉ số 0, tăng -> {1, 1, 1, 1}
Chỉ số 1, tăng -> {1, 2, 2, 2}
Chỉ số 1, tăng -> {1, 3, 3, 3}
Chỉ số 1, tăng -> {1, 4, 4, 4}
Chỉ số 2, tăng -> {1, 4, 5, 5}
Chỉ số 3, giảm -> {1, 4, 5, 4}
Chỉ số 3, giảm -> {1, 4, 5, 3}
Tổng = 7

Phương pháp sử dụng

Nếu mảng ban đầu là B[]. Để B[0] = arr[0], cần arr[0] phép tăng hậu tố. Sau đó B[0]=B[1]=...=B[n-1]=arr[0].

Để B[1] = arr[1], cần |arr[1] - arr[0]| phép toán (tăng hoặc giảm).

Để B[i] = arr[i], cần |arr[i] - arr[i-1]| phép toán.

Tổng phép toán = |arr[0]| + |arr[1]-arr[0]| + ... + |arr[n-1]-arr[n-2]|.

• Nhập mảng mục tiêu arr[]
• Hàm incr_decr_op(int arr[], int size) trả về số phép toán
• Khởi tạo count = 0
• Duyệt mảng: chỉ số 0 cộng arr[i], chỉ số khác cộng abs(arr[i]-arr[i-1])
• Trả về count

Chương trình minh họa

#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 += abs(arr[i]);
    }
    return count;
}

int main() {
    int arr[] = {3, 3, 1, 2, 2};
    int size = sizeof(arr) / sizeof(arr[0]);
    cout << "Số phép toán hậu tố tăng/giảm để xây mảng mục tiêu là: " << incr_decr_op(arr, size) << endl;
    return 0;
}

Đầu ra

Số phép toán hậu tố tăng/giảm để xây mảng mục tiêu là: 6