Cho mảng A với n phần tử. Có thể chọn bất kỳ tập con nào và đổi dấu các phần tử trong tập con đó. Hãy tìm số lượng giá trị khác nhau tối đa có thể có trong mảng sau thao tác.
Ví dụ
Với A = [1, 1, 2, 2], đầu ra là 4. Có thể đổi dấu phần tử đầu và cuối thành [-1, 1, 2, -2] có 4 giá trị khác nhau.
Giải thuật
Sử dụng tập hợp (set) để lưu các giá trị đã xử lý. Duyệt mảng: nếu giá trị x đã có trong tập hợp, thêm -x vào; ngược lại thêm x. Kích thước tập hợp cuối cùng là kết quả.
Mã C++
#include <bits/stdc++.h>
using namespace std;
int solve(vector<int> A) {
set<int> se;
int n = A.size();
for (int i = 0; i < n; i++) {
int x = A[i];
if (se.count(x))
se.insert(-x);
else
se.insert(x);
}
return se.size();
}
int main() {
vector<int> A = { 1, 1, 2, 2 };
cout << solve(A) << endl;
}
Đầu vào / Đầu ra
Input: { 1, 1, 2, 2 }
Output: 4