Giả sử chúng ta có một mảng A với n phần tử khác nhau. Một mảng B được gọi là đẹp nếu với bất kỳ hai phần tử khác nhau B[i] và B[j], |B[i] - B[j]| xuất hiện trong B ít nhất một lần, và tất cả các phần tử trong B đều khác nhau. Chúng ta phải kiểm tra xem có thể thêm một số số nguyên vào A để làm cho nó đẹp với kích thước tối đa 300 hay không. Nếu có thể trả về mảng mới, ngược lại trả về -1.
Ví dụ, nếu đầu vào là A = [4, 8, 12, 6], thì đầu ra sẽ là [8, 12, 6, 2, 4, 10], vì |4-2| = |6-4| = |8-6| = |10-8| = |12-10| = 2 có trong mảng, |6-2| = |8-4| = |10-6| = |12-8| = 4 có trong mảng, |8-2| = |10-4| = |12-6| = 6 có trong mảng, |10-2| = |12-4| = 8 có trong mảng, và |12-2| = 10 có trong mảng, nên mảng là đẹp. (Các đáp án khác cũng có thể)
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 t := 0 b := 0 for khởi tạo i := 0, khi i < n, cập nhật (tăng i lên 1), do: a := A[i] if a < 0, thì: t := 1 b := maximum của a và b if t khác 0, thì: in -1 Ngược lại for khởi tạo i := 0, khi i <= b, cập nhật (tăng i lên 1), do: in i
Ví dụ
Xem triển khai sau để hiểu rõ hơn:
#include <bits/stdc++.h> using namespace std; void solve(vector<int> A) { int n = A.size(); int t = 0; int b = 0; for (int i = 0; i < n; i++) { int a = A[i]; if (a < 0) t = 1; b = max(a, b); } if (t) cout << "-1"; else { for (int i = 0; i <= b; i++) cout << i << ", "; } } int main() { vector<int> A = { 4, 8, 12, 6 }; solve(A); }Đầu vào
{ 4, 8, 12, 6 }Đầu ra
0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12,