Đếm cặp có tổng bằng 0

Tác giả:

nvatuan

Dạng bài

Điểm: 200 (p) Thời gian: 1.0s Bộ nhớ: 256M Input: bàn phím Output: màn hình

Cho dãy số \(A\) có \(N\) số nguyên. Hãy đếm số cặp \((i,j)\) sao cho \(A_i + A_j = 0\), với \(i < j\).

Input

Dòng đầu tiên chứa một số nguyên dương \(N\) \((1 \leq N \leq 2*10^5)\)
Dòng thứ hai chứa dãy số \(A\) gồm \(N\) số nguyên cách nhau bởi một ký tự khoảng trống. \((|A_i| \leq 10^9)\)

Output

In ra một số nguyên duy nhất, là số cặp phần tử trong dãy \(A\) mà có tổng là 0.

Scoring

Subtask \(1\) (\(25\%\) số điểm): \(N \leq 10^4\), \(|A_i| \leq 10^6\).
Subtask \(2\) (\(60\%\) số điểm): \(N \leq 2*10^5\), \(|A_i| \leq 10^6\).
Subtask \(3\) (\(100\%\) số điểm): \(N \leq 2*10^5\), \(|A_i| \leq 10^9\).

Example

Test 1

Input

3
-2 0 2

Output

Note

Chỉ tồn tại một cặp phần tử \((1, 3)\) tương ứng với \(A_1 + A_3 = -2 + 2 = 0\).

Test 2

Input

6
-2 -1 0 0 1 2

Output

Bình luận

Delphi

var x,l,r,m,n,i,j,k,temp:longint;
a:array [1..100000000] of longint;
function tknp(x:longint):longint;
begin
l:=1;r:=n;
while l <= r do
begin
    m:=(l+r) div 2;
    if a[m] = x then exit(m);
    if a[m] > x then r:=m-1 else l:=m+1;
    if l >r then exit(0);
end;
exit(0);
end;
begin
    readln(n);
    for i:=1 to n do read(a[i]);
    for i:=1 to n-1 do
    for j:=i+1 to n do
    if a[i] > a[j] then
    begin
    temp:=a[i];
    a[i]:=a[j];
    a[j]:=temp;
    end;
    for i:=1 to n do if tknp(-a[i]) <> 0 then inc(k);
    write(k div 2);
end.

0

lamsauday246 8:00 p.m. 2 Tháng 10, 2022 ← đã chỉnh sửa →

if(a[i]=(-a[j]))then dem:=dem+1;

0

rukashii 8:19 p.m. 18 Tháng 11, 2021

dùng đếm pp đi ❤️

0

minhtuanitk20 10:04 p.m. 17 Tháng 11, 2021

em làm j mà chặt nhị phân đồ phức tạp thế

2 bình luận nữa