양의 정수를 포함하는 대상 배열 arr[]이 제공됩니다. 목표는 모두 0인 초기 배열을 사용하여 대상 배열 arr[]를 구성하는 것입니다. 주어진 빈 배열에 적용할 수 있는 연산이 모두 0인 경우 증가/감소 연산이 접미사에 붙습니다.
i라고 하는 인덱스를 선택하면 접미사 증가 연산의 경우 인덱스 i에서 마지막 인덱스까지 모든 요소에 1을 추가합니다.
접미사 감소 연산의 경우 인덱스 i에서 마지막 인덱스까지 모든 요소에서 1을 뺍니다.
예를 들어 이해하자
입력 - arr[]={ 1,2,3 }
출력 - 주어진 배열을 구성하기 위한 접미사 증가/감소 연산의 수는 - 3
설명
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 입력 - arr[]={ 1, 4, 5, 3 }
출력 - 주어진 배열을 구성하기 위한 접미사 증가/감소 연산의 수는 - 7
설명
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 아래 프로그램에서 사용된 접근 방식은 다음과 같습니다.
초기 배열을 B[ ]로 취하면. 첫 번째 요소 B[0]을 arr[0]과 같게 만들기 위해. arr[0] 수의 접미사 증가 작업이 필요합니다. 이 후 모든 B[0]=B[1]....=B[n-1]=arr[0]이 동일합니다.
두 번째 요소 B[1]을 arr[1]과 같게 하려면 | arr[1]-arr[0] | 작업 수. (증가 또는 감소).
따라서 B[i]를 arr[i]와 같게 하려면 | arr[i]- arr[i-1] | 작업 수.
총 작업 수는 | arr[0] | + | arr[1]-arr[0] | + … + | arr[n-1]-arr[n-2] |.
-
대상 배열을 arr[]로 사용합니다.
-
함수 incr_decr_op(int arr[], int size)는 배열과 배열의 길이를 가져와서 주어진 배열을 구성하기 위한 접미사 증가/감소 연산의 수를 반환합니다.
-
초기 카운트를 0으로 합니다.
-
for 루프를 사용하여 배열 arr[] 순회
-
인덱스 0의 경우 arr[i]를 추가하여 계산합니다.
-
다른 인덱스의 경우 abs( arr[i]-arr[i-1] )를 추가하여 계산합니다.
-
for 루프가 끝나면 결과로 count를 반환합니다.
예
#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;
} 출력
위의 코드를 실행하면 다음과 같은 출력이 생성됩니다 -
Count of suffix increment/decrement operations to construct a given array are: 6