Sorting Algorithm
Xem dạng PDF
Gửi bài giải
Điểm:
20,00 (OI)
Giới hạn thời gian:
1.0s
Giới hạn bộ nhớ:
256M
Input:
stdin
Output:
stdout
Nguồn bài:
Dạng bài
Ngôn ngữ cho phép
C, C++, Java, Kotlin, Pascal, PyPy, Python, Scratch
cho bạn một dãy ~A~ gồm ~n~ phần tử và muốn bạn hãy sắp xếp mảng lại thành một mảng không giảm.
Nhưng lại thấy bài toán này khá là đơn giản nên cậu ta sẽ cho bạn biến đổi mảng ~A~ như sau:
Chọn 2 chỉ số ~i~ và ~j~ ~(1 \le i < j \le n)~
Xóa 2 phần tử ~A_i~ và ~A_j~
Chèn vào mảng tổng của ~A_i~ và ~A_j~ ở vị trí bất kì
Hãy lặp lại thao tác này cho đến khi dãy ~A~ ban đầu trở thành dãy không giảm.
Yêu cầu: Hãy đếm số lần biến đổi nhỏ nhất để mảng ~A~ trở thành mảng không giảm
INPUT
- Dòng đầu chứa số ~n~ ~(1 \le n \le 2.10^5)~
- Dòng tiếp là dãy ~A~ gồm ~n~ phần tử ~(1 \le A_i \le 10^6)~
OUTPUT
- Gồm một số nguyên dương là yêu cầu của bài toán
SUBTASKS
- Subtask 1 (30%): ~n \le 10^4~
- Subtask 2 (70%): ~n \le 2.10^5~
SAMPLE
Input
5
1 3 2 2 5
Output
1
Explanation
- Ta chọn i = 2 và j = 3
- Xóa A[2] và A[3]
- Chèn vào cuối mảng tổng của A[2] + A[3] = 3 + 2 = 5
-> Mảng sau khi biến đổi: 1 2 5 5
-> Thỏa mãn yêu cầu bài toán là biến đổi thành dãy không giảm
-> Chỉ tốn 1 lần biến đổi
Bình luận
cuối cùng thì :))
Đã sinh lại test rồi nhé. C.ơn TNNC vì đã làm chuột bạch
🥰
Test hiện giờ đang yếu nên sẽ được sinh lại
bộ test ok rồi nha mng
bài này quen lắm nè hình như từng làm 1 lần rồi
bài này sử dụng qhđ nên mấy e ch học thì qua bài khác nha. bài này a định thêm vào contest cnp & qhđ mà thầy lỡ up rồi nên thôi
sinh test lẹ đê
hiện tại account của a đang bị lỗi nên chx thêm test vô được. mng thông cảm
Dạ anh Shinoz đẹp zai ơi, mong anh sửa lại ở chỗ yêu cầu á anh: đếm chớ ko phải đến hihi
ok e
Làm rồi sao nộp được ạ
nộp bài kiểu j
Dạ chắc anh Shinoz đẹp zai chưa đẩy test để chấm