เราได้รับอาร์เรย์เป้าหมาย arr[] ที่มีจำนวนเต็มบวก เป้าหมายคือสร้างอาร์เรย์เป้าหมาย arr[] โดยใช้อาร์เรย์เริ่มต้นที่มีแต่ 0 การดำเนินการที่สามารถนำไปใช้กับอาร์เรย์ว่างที่มีแต่ 0 จะเป็นการดำเนินการเพิ่ม/ลดแบบซัฟฟิกซ์ (suffix increment/decrement operations)
ถ้าเราเลือกดัชนีใดๆ เช่น i ในกรณีของการดำเนินการเพิ่มแบบซัฟฟิกซ์ เราจะบวก 1 ให้กับองค์ประกอบทั้งหมดจากดัชนี i จนถึงดัชนีสุดท้าย
ในกรณีของการดำเนินการลดแบบซัฟฟิกซ์ เราจะลบ 1 จากองค์ประกอบทั้งหมดจากดัชนี i จนถึงดัชนีสุดท้าย
ตัวอย่าง
อินพุต - arr[] = {1, 2, 3}
เอาต์พุต - จำนวนการดำเนินการเพิ่ม/ลดแบบซัฟฟิกซ์เพื่อสร้างอาร์เรย์ที่กำหนดคือ - 3
คำอธิบาย
เริ่มจาก {0, 0, 0}
เลือกดัชนี 0, ใช้การเพิ่มแบบซัฟฟิกซ์ {1, 1, 1}
เลือกดัชนี 1, ใช้การเพิ่มแบบซัฟฟิกซ์ {1, 2, 2}
เลือกดัชนี 2, ใช้การเพิ่มแบบซัฟฟิกซ์ {1, 2, 3}
รวมการดำเนินการ = 3
อินพุต - arr[] = {1, 4, 5, 3}
เอาต์พุต - จำนวนการดำเนินการเพิ่ม/ลดแบบซัฟฟิกซ์เพื่อสร้างอาร์เรย์ที่กำหนดคือ - 7
คำอธิบาย
เริ่มจาก {0, 0, 0, 0}
เลือกดัชนี 0, ใช้การเพิ่มแบบซัฟฟิกซ์ {1, 1, 1, 1}
เลือกดัชนี 1, ใช้การเพิ่มแบบซัฟฟิกซ์ {1, 2, 2, 2}
เลือกดัชนี 1, ใช้การเพิ่มแบบซัฟฟิกซ์ {1, 3, 3, 3}
เลือกดัชนี 1, ใช้การเพิ่มแบบซัฟฟิกซ์ {1, 4, 4, 4}
เลือกดัชนี 2, ใช้การเพิ่มแบบซัฟฟิกซ์ {1, 4, 5, 5}
เลือกดัชนี 3, ใช้การลดแบบซัฟฟิกซ์ {1, 4, 5, 4}
เลือกดัชนี 3, ใช้การลดแบบซัฟฟิกซ์ {1, 4, 5, 3}
รวมการดำเนินการ = 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) รับอาร์เรย์และความยาว คืนค่าจำนวนการดำเนินการเพิ่ม/ลดแบบซัฟฟิกซ์เพื่อสร้างอาร์เรย์ที่กำหนด
- ตั้งค่า count เริ่มต้นเป็น 0
- เดินทางผ่านอาร์เรย์ arr[] โดยใช้ลูป for
- สำหรับดัชนี 0 บวก arr[i] เข้า count
- สำหรับดัชนีอื่นๆ บวก abs(arr[i]-arr[i-1]) เข้า count
- ที่สิ้นสุดของลูป 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
