Chúng ta được cho một mảng target[] chứa các số. Chúng ta phải tìm số bước tối thiểu mà mảng toàn 0 [0,0,0,0...] có thể chuyển thành target chỉ dùng hai phép toán sau:
- Phép tăng (Increment) − tất cả phần tử có thể tăng 1, mỗi phép tăng trên mỗi phần tử được đếm riêng trong số bước. (cho n phép tăng trên n phần tử thì steps = n)
- Phép nhân đôi (Doubling) − toàn bộ mảng được nhân đôi. Với tất cả phần tử nó được đếm một lần. (mỗi phép nhân đôi nhân đôi giá trị tất cả phần tử, đếm là 1 trong steps)
Mục tiêu là tìm số bước tối thiểu để đạt target. Ví dụ [0,0,0] có thể thành [1,1,1] trong 3 bước tối thiểu (bằng phép tăng trên tất cả phần tử) và có thể thành [2,2,2] bằng thêm một phép nhân đôi, tổng 4 bước lần này (3 phép tăng, 1 phép nhân đôi).
Ví dụ
Đầu vào
target[] = { 1, 2, 2, 3 }
Đầu ra
Số bước tối thiểu từ {0,0,0,0}: 6
Giải thích
Ban đầu chúng ta có {0,0,0,0}
3 phép tăng {0,1,1,1} // phép tăng xảy ra riêng lẻ
1 phép nhân đôi {0,2,2,2} // nhân đôi xảy ra trên tất cả phần tử
2 phép tăng {1,2,2,3}
Tổng bước = 3 + 1 + 2 = 6
Đầu vào
target[] = { 3, 3, 3 }
Đầu ra
Số bước tối thiểu từ {0,0,0}: 7
Giải thích
Ban đầu {0,0,0}
3 phép tăng {1,1,1}
1 phép nhân đôi {2,2,2}
3 phép tăng {3,3,3}
Tổng bước = 3 + 1 + 3 = 7
Phương pháp sử dụng trong chương trình dưới đây
- Mảng số nguyên target[] lưu các phần tử mục tiêu cần đạt.
- Hàm minSteps(int target[], int n) nhận mảng target và độ dài 'n', trả về số bước tối thiểu để đạt target từ toàn 0.
- Biến count lưu số bước, khởi tạo 0.
- Biến max lưu phần tử lớn nhất, khởi tạo target[0].
- Biến pos lưu chỉ số của max tìm thấy, khởi tạo 0.
- Nếu mảng target[] toàn 0 thì trả về 0 vì không cần bước. (for i=0 đến n nếu target[i]==0 count++; nếu count==n // toàn 0)
- Bây giờ trong phương pháp này chúng ta sẽ từ target[] về toàn 0.
- Làm cho tất cả phần tử chẵn bằng cách trừ 1 từ các phần tử lẻ. Tăng count cho mỗi phép trừ (tương tự phép tăng).
- Bây giờ ta có toàn số chẵn.
- Cũng tìm giá trị max và vị trí của nó trong cùng vòng lặp và khởi tạo max và pos.
- Bây giờ bắt đầu chia toàn mảng cho 2 cho đến khi giá trị max không thành 1. Nếu số nào thành lẻ, trừ 1 và tăng count, cho phép chia toàn bộ tăng count một lần.
- Cuối cùng tất cả phần tử sẽ là 0 hoặc 1, với tất cả 1 làm chúng thành 0 và tăng count lại.
- Trả về kết quả là số bước trong count.
Ví dụ mã nguồn
#include <bits/stdc++.h>
using namespace std;
int minSteps(int target[], int n) {
int i;
int count = 0;
int max = target[0];
int pos = 0;
for (i = 0; i < n; i++)
if (target[i] == 0)
count++;
// nếu toàn 0, giống target
if (count == n)
return 0;
count = 0;
// làm tất cả chẵn bằng trừ 1
for (i = 0; i < n; i++) {
if (target[i] % 2 == 1) {
target[i] = target[i] - 1;
count++;
}
// tìm max và vị trí
if (target[i] >= max) {
max = target[i];
pos = i;
}
}
// chia cho 2 cho đến khi tất cả phần tử là 1 và tăng count một lần
while (target[pos] != 1) {
for (i = 0; i < n; i++) {
if (target[i] % 2 == 1) {
target[i] = target[i] - 1;
count++;
}
target[i] = target[i] / 2;
}
count++;
}
// toàn mảng {1} làm 0 và tăng count
while (target[pos] != 0) {
for (i = 0; i < n; i++) {
if (target[i] != 0) {
target[i] = target[i] - 1;
count++;
}
}
}
return count;
}
int main() {
int target[] = {15, 15, 15};
cout << "\nSố bước tối thiểu để đạt mảng mục tiêu: " << minSteps(target, 3);
return 0;
}
Kết quả
Số bước tối thiểu để đạt mảng mục tiêu: 15