Giả sử chúng ta có một mảng A với n phần tử. Xét có một mật khẩu với n số nguyên dương. Chúng ta áp dụng các phép toán sau trên mảng. Phép toán là loại bỏ hai phần tử liền kề không giống nhau, sau đó đặt tổng của chúng tại vị trí đó. Vì vậy, phép toán này sẽ giảm kích thước mảng đi 1. Chúng ta phải tìm độ dài ngắn nhất có thể của mảng sau khi thực hiện các phép toán này.
Ví dụ, nếu đầu vào là A = [2, 1, 3, 1], thì đầu ra sẽ là 1, vì nếu chọn (1, 3), mảng sẽ thành [2, 4, 1], rồi chọn (2, 4) làm mảng [6, 1], rồi chọn hai cuối để được [7].
Các bước
Để giải quyết bài toán này, chúng ta sẽ làm theo các bước sau:
n := kích thước của A Định nghĩa một tập hợp se for khởi tạo i := 0, khi i < n, cập nhật (tăng i lên 1), do: chèn A[i] vào se if kích thước của se bằng 1, thì: return n Ngược lại return 1
Ví dụ
Xem triển khai sau để hiểu rõ hơn:
#include <bits/stdc++.h> using namespace std; int solve(vector<int> A) { int n = A.size(); set<int> a; for (int i = 0; i < n; i++) { a.insert(A[i]); } if (a.size() == 1) return n; else return 1; } int main() { vector<int> A = { 2, 1, 3, 1 }; cout << solve(A) << endl; }Đầu vào
{ 2, 1, 3, 1 }Đầu ra
1