LRC_1B - Chọn cặp

View as PDF

Submit solution

Points: 1.00 (partial)
Time limit: 1.0s
Memory limit: 256M
Input: stdin
Output: stdout

Authors:
Problem type

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~.


Comments

Please read the guidelines before commenting.



  • 2
    dinhvantung0611  commented on Jan. 29, 2024, 1:53 p.m.

    Ý 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