#1212. DELARR - Xóa dãy

Bộ nhớ: 256 MiB Thời gian: 1000 ms Nhập/xuất từ luồng chuẩn
Kiểu bài: Thông thường Kiểu chấm: So sánh văn bản
Đưa lên bởi: Chùm CUỐI

Đề bài

Nguồn: Ôn HN tháng 11/2017, Thầy Lê Minh Hoàng, Ngày 1

Cho dãy số nguyên 𝐴 = (𝑎_0, 𝑎_1, … , 𝑎_{𝑛−1}) . Bạn được phép xóa đi một phần tử có giá trị nhỏ nhất hoặc xóa đi một phần tử có giá trị lớn nhất trong dãy.

Yêu cầu: Tìm cách dùng ít nhất các phép xóa theo luật trên để thu được một dãy mới có tổng các phần tử trong dãy bằng 0 . (Dãy rỗng cũng được coi là dãy có tổng các phần tử bằng 0 ).

Dữ liệu vào:

  • Dòng đầu chứa số nguyên dương 𝑛 ≤ 10^5 ;
  • Dòng thứ hai chứa 𝑛 số nguyên 𝑎_0, 𝑎_1, … , 𝑎_{𝑛−1} cách nhau bởi dấu cách (∀𝑖: |𝑎_𝑖| ≤ 10^9) .

Dữ liệu ra:

  • Ghi ra một số nguyên duy nhất là số phép xóa cần thực hiện.

Ví dụ:

Dữ liệu vào:
-4 -5 1 2 -3 10
Dữ liệu ra:
3
Dữ liệu vào:
8
-3 -3 -3 0 0 0 4 4
Dữ liệu ra:
5
Dữ liệu vào:
9
1 2 3 4 5 6 7 8 9
Dữ liệu ra:
9