Xin ý tưởng thuật toán cho bài tập
Đề bài như sau ạ :
Hôm nay là ngày đầu tiên JK đi học. JK được giao một bài tập về nhà như sau:
Thầy giáo có một mảng n số nguyên không âm. Thầy muốn tìm 1 số nguyên x, sau đó cộng thêm x vào một số phần tử của mảng (không quá 1 lần với mỗi phần tử), và trừ đi x vào một số phần tử của mảng (không quá 1 lần với mỗi phần tử), sao cho sau đó tất cả các phần tử của mảng đều bằng nhau.
Với mảng n số nguyên ban đầu thầy cho, JK phải trả lời thầy rằng có tồn tại số nguyên x thỏa mãn hay không?
Hãy giúp JK ghi điểm ngay buổi đầu đi học nhé!
Input
Dòng đầu tiên chứa số nguyên n (1 ≤ n ≤ 105) - số lượng phần tử trong mảng Dòng thứ hai chứa n số nguyên a1 , a2 , … , an (0 ≤ ai ≤ 109) - các phần tử của mảng.
Output
Nếu không tồn tại số nguyên x làm cho tất cả các phần tử của mảng bằng nhau, in "NO, ngược lại in " YES ".
Example
Input:
5
1 3 3 2 1
Output:
YES
Input:
5
1 2 3 4 5
Output:
NO
Mình mong được mọi người giúp đỡ ạ =))
Giả sử có một số nguyên X
Các giá trị trong mảng có thể có các giá trị:
a0 + X
a1
a2 - X
Sao cho a0 + X == a1 == a2 - X
một mảng thoả mãn điều kiện trên cần có
Tức là trong mảng chỉ có các số nguyên a, a + x, a - x (a là 1 số bất kì).
Ta chỉ cần sort lại mảng, kiểm tra xem:
Có tối đa 3 số khác nhau hay không (nếu ít hơn 3 thì càng tốt, ta chỉ cần cộng/trừ 1 lần), ví dụ như 1 3 2 2 1 có 3 số khác nhau (1, 2, 3). Nếu có thì YES, nếu không thì NO.
Nếu có 3 số khác nhau, kiểm tra xem (số lớn nhất + số nhỏ nhất) / 2 (chia hết) có nằm trong dãy không. Nếu có thì YES, nếu không thì NO.
Do ta chỉ cần nhận diện 3 số nên việc sort có thể tránh được, tức chỉ cần đọc 3n lần.
Bài này for 1 n cũng được, nhưng mà nhiều if else quá.
for j:=1 to flag_counter do mấy số cũng được, chốt bằng một câu if.
Với test 1 2 2 3 4 thì sao ạ .Nó là 4 số khác nhau. Nhưng vẫn đúng chứ
Đúng gì mà đúng. Bạn chọn x bằng bao nhiêu đây? Mảng sau cùng là như thế nào?
À ừ mình nhầm. @@ Mình cảm ơn :v