เราได้รับอาร์เรย์เป้าหมาย arr[] ที่มีจำนวนเต็มบวก เป้าหมายคือการสร้างอาร์เรย์เป้าหมาย arr[] โดยใช้อาร์เรย์เริ่มต้นที่มี 0 ทั้งหมด การดำเนินการที่สามารถนำไปใช้กับอาร์เรย์ว่างที่กำหนดโดยมีค่า 0 ทั้งหมดจะต่อท้ายการดำเนินการเพิ่ม/ลด
หากเราเลือกดัชนีใด ๆ ที่บอกว่า i ในกรณีของการดำเนินการเพิ่มส่วนต่อท้าย เราจะเพิ่ม 1 ให้กับองค์ประกอบทั้งหมดตั้งแต่ดัชนี i จนถึงดัชนีสุดท้าย
ในกรณีของการดำเนินการลดส่วนต่อท้าย เราจะลบ 1 จากองค์ประกอบทั้งหมดจากดัชนี i จนถึงดัชนีสุดท้าย
ให้เราเข้าใจด้วยตัวอย่าง
ป้อนข้อมูล − 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
-
Traverse array arr[] ใช้ for loop
-
สำหรับดัชนี 0 ให้เพิ่ม arr[i] เพื่อนับ
-
สำหรับดัชนีอื่น ๆ ให้เพิ่ม abs( arr[i]-arr[i-1] ) เพื่อนับ
-
ที่ส่วนท้ายของ for loop return นับเป็นผลลัพธ์
ตัวอย่าง
#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
