Dãy "Lên bờ xuống ruộng"
Xem PDF
Điểm:
250
Thời gian:
1.0s
Bộ nhớ:
256M
Input:
bàn phím
Output:
màn hình
Cho dãy \(a\) gồm \(n\) phần tử \(a_1,a_2,...,a_n\).
Dãy \(a\) được gọi là dãy "Lên bờ xuống ruộng" nếu tồn tại phần tử \(i(1\le i\le n)\) thoả mãn : \(a_1<a_2<...<a_{i-1}<a_i>a_{i+1}>...>a_{n-1}>a_n\).
Yêu cầu: Cho một dãy \(b\) gồm \(m\) phần tử \(b_1,b_2,...,b_m\) bất kì. Nhiệm vụ của bạn là từ mảng \(b\) chọn ra các phần tử để tạo thành dãy \(a\) sao cho \(a\) là dãy "Lên bờ xuống ruộng" và số lượng phần tử của dãy \(a\) là nhiều nhất có thể. Nếu có nhiều đáp án, in ra bất kì.
Input
- Dòng thứ nhất chứa số nguyên \(m\)
- Dòng thứ hai chứa \(m\) số nguyên \(b_1,b_2,...,b_m\)
Output
- Dòng thứ nhất chứa số lượng phần tử của dãy \(a\)
- Dòng thứ hai thể hiện các phần tử của dãy \(a\)
Constraints
- \(1\leq m\leq 10^5\)
- \(1\leq b_i\leq 5000\)
Example
Test 1
Input
3
1 2 3 Output
3
1 2 3
Bình luận
Ủa sao đề nói a1<a2<...<ai−1\<ai>ai+1>...>an−1>an mà sao test vd ra 1 2 3 ai giải thích đề giùm em với
-
1
jumptozero
6:18 a.m. 24 Tháng 2, 2021
-
1
nguyendanghau2006
5:12 p.m. 8 Tháng 2, 2022
1 bình luận nữaĐối với dãy \(1,2,3\). Thì chỉ số \(i\) sẽ bằng \(3\). Tức là ta có dãy: \(a_1<a_2<a_3(1<2<3)\). Còn đối với dãy \(3,2,1\). Thì chỉ số \(i\) sẽ bằng \(1\). Tức là ta có dãy: \(a_1>a_2>a_3(3>2>1)\)
bài này thực chất là sort lại rồi xoá các phần tử giống nhau thôi đúng ko anh