เราได้รับอาเรย์ target[] ที่มีตัวเลข ต้องหาขั้นตอนน้อยที่สุดที่อาเรย์ศูนย์ [0,0,0,0...] สามารถกลายเป็น target[] ได้โดยใช้ 2 การดำเนินการเท่านั้น:
- Increment operation − เพิ่มทุกสมาชิกทีละ 1 แต่ละครั้งนับ 1 ขั้นตอน (n ครั้งสำหรับ n สมาชิก = n steps)
- Doubling operation − คูณอาเรย์ทั้งอาเรย์ด้วย 2 นับ 1 ขั้นตอน (ทุกสมาชิกคูณ 2 นับ 1 step)
เป้าหมายคือหา minimum steps เพื่อถึง target เช่น [0,0,0] → [1,1,1] ใช้ 3 steps (increment ทุกตัว) → [2,2,2] ใช้ doubling 1 ครั้ง รวม 4 steps
อินพุต
target[] = {1, 2, 2, 3}
เอาต์พุต
Minimum steps to reach target from {0,0,0,0}: 6
คำอธิบาย − เริ่ม {0,0,0,0} → 3 increments → {0,1,1,1} → 1 doubling → {0,2,2,2} → 2 increments → {1,2,2,3} รวม 3+1+2=6
อินพุต
target[] = {3, 3, 3}
เอาต์พุต
Minimum steps to reach target from {0,0,0}: 7
คำอธิบาย − 3 increments → {1,1,1} → 1 doubling → {2,2,2} → 3 increments → {3,3,3} รวม 7
วิธีการที่ใช้ในโปรแกรมด้านล่าง
- อาเรย์ target[] เก็บค่าเป้าหมาย
- ฟังก์ชัน minSteps(int target[], int n) คืนค่าขั้นตอนน้อยที่สุด
- count นับ steps, max เก็บค่าสูงสุด, pos เก็บ index ของ max
- ถ้า target[] เป็นศูนย์หมด คืน 0
- วิธีนี้ทำย้อนกลับ: จาก target[] กลับไปสู่ศูนย์
- ทำให้ทุกตัวเป็นเลขคู่โดยลบ 1 จากเลขคี่ (นับ steps)
- หา max และ pos ในลูปเดียวกัน
- หารอาเรย์ทั้งอาเรย์ด้วย 2 จนกว่า max จะกลายเป็น 1 (ถ้าตัวไหนคี่ ลบ 1 ก่อน แล้วค่อยหาร นับ steps)
- สุดท้ายทุกตัวจะเป็น 0 หรือ 1 ทำให้เป็น 0 ทั้งหมด (นับ steps)
- คืนค่า count
ตัวอย่างโค้ด
#include <bits/stdc++.h>
using namespace std;
int minSteps(int target[], int n) {
int count = 0;
int max = target[0];
int pos = 0;
for (int i = 0; i < n; i++)
if (target[i] == 0) count++;
if (count == n) return 0;
count = 0;
for (int i = 0; i < n; i++) {
if (target[i] % 2 == 1) {
target[i]--;
count++;
}
if (target[i] >= max) {
max = target[i];
pos = i;
}
}
while (target[pos] != 1) {
for (int i = 0; i < n; i++) {
if (target[i] % 2 == 1) {
target[i]--;
count++;
}
target[i] /= 2;
}
count++;
}
while (target[pos] != 0) {
for (int i = 0; i < n; i++) {
if (target[i] != 0) {
target[i]--;
count++;
}
}
}
return count;
}
int main() {
int target[] = {15, 15, 15};
cout << "\nMinimum steps to get the given desired array: " << minSteps(target, 3);
return 0;
}
ผลลัพธ์
Minimum steps to get the given desired array: 15
