LRC_1B - Chọn cặp
Xem dạng PDF
Gửi bài giải
Điểm:
1,00 (OI)
Giới hạn thời gian:
1.0s
Giới hạn bộ nhớ:
256M
Input:
stdin
Output:
stdout
Tác giả:
Dạng bài
Cho một mảng ~a~ gồm ~N~ số nguyên. Với mỗi thao tác, thì bạn sẽ chọn ra hai vị trí ~i~, ~j~ (~i~, ~j~ ~\le~ ~N~) khác nhau sao cho ~a_i + a_j~ ~\ge~ 0 và xóa nó đi khỏi mảng, khi xóa thì thứ tự các vị trí còn lại vẫn giữ nguyên.
Hãy tìm cách thực hiện thao tác sao cho số lượng phần tử trong mảng ~a~ là ít nhất.
Dữ liệu
Dòng đầu tiên chứa số ~N~ ~(3 \le N \le 10^5)~ Dòng tiếp theo chứa ~N~ số nguyên ~a_1~, ~a_2~, ~a_3~ ,....., ~a_n~ ~(|a_i| \le 10^9)~.
Kết quả
In ra số thao tác đã thực hiện.
Test ví dụ
Dữ liệu
5
-1 2 5 -1 3
Kết quả
2
Giải thích
Thao tác 1 : Lấy hai số có vị trí là 1 và 5 ra khỏi mảng.
Sau khi thực hiện thì mảng còn lại ~(2, 5, -1)~.
Thao tác 2 : Lấy hai số có vị trí là 2 và 3 ra khỏi mảng.
Sau khi thực hiện thì mảng còn lại duy nhất ~2~.
Bình luận
Ý tưởng: Thực chất bài này yêu cầu đó là đếm số cặp sao cho ai + aj >= 0 (1 <= i, j <= N, i != j). Vậy ta chỉ cần tìm i, j sao cho chúng không trùng nhau là được i > j hay j < i cũng đều thoả mãn (miễn là i != j).
Vậy ta trước tiên sort lại mảng: Ta sẽ được 1 dãy số tăng dần. Sử dụng 2 con trỏ (a = A[1], b = A[N]), lúc này ta sẽ cộng số nhỏ nhất và số lớn nhất trong mảng lại với nhau. Nếu nó >= 0 thì số cặp của ta +1, a++ và b--. Ngược lại thì ta chỉ việc a++ để sang số tiếp theo, cứ như vậy đến khi a >= b thì dừng.
Ví dụ: Ta có mảng là [-99, -1, 1, 2, 4, 5] (mảng đã sort). a chỉ vào -99 và b chỉ vào 5. Nhận thấy ngay a + b < 0 (-99 + 5 < 0) vậy a++ để sang -1, lúc này a + b >= 0 (-1 + 5 >= 0). Số cặp sẽ +1, a++, b-- để sang cặp tiếp theo. Tiếp tục cặp (1, 4) tương tự và cuối cùng khi a = 2, b = 2 (a và b cùng chỉ vào 1 phần tử) ta break không duyệt nữa do 1 phần tử không thể tạo thành 1 cặp.
Nếu bạn hiểu và áp dụng phương pháp của mình, giúp mình 1 up vote nhé. Cảm ơn các bạn.
CƯỜNG GIẢ HỌ ĐINH, VẠN CỔ TỐI CƯỜNG. CAO CAO TẠI THƯỢNG, DUY NGÃ ĐỘC TÔN