Số bạn bè
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
Bạn được cho dãy số nguyên dương a có ~N~ phần tử. Một số được xem là có bạn bè nếu tồn tại ~i≠j~ mà ~A_i = A_j~.
Yêu cầu: In ra số lượng phần tử có bạn bè.
Dữ liệu vào
- Dòng 1. Ghi số nguyên dương ~N~.
- Dòng 2. Chứa ~N~ số nguyên dương là các phần tử của mảng.
Dữ liệu ra
- Một dòng duy nhất chứa đáp án cần tìm.
Ví dụ
Input
6
1 1 1 4 3 3
Output
2
Subtask
- Subtask 1 (50%): ~n \le 10^3; A_i \le 10^9~
- Subtask 2 (30%): ~n \le 10^6; A_i \le 10^6~
- Subtask 3 (20%): ~n \le 10^5; A_i \le 10^9~
Bình luận
lại bị đề lùa =)))
ai giai thích giùm mik out sao lại ra 2 nhỉ :/
Ta sẽ sắp xếp lại dãy theo thứ tự tăng dần, sau đó duyệt qua từng phần tử, nếu a[i]:=a[i]-1 thì ta sẽ tăng biến kết quả lên.
Lưu ý trường hợp bị cộng lặp( VD :1 3 3 3 ) Độ phức tạp : O(Nlog(N))
out ra 5 chứ :xDDD
nó là 1 cặp mà a =))))))))))))))))))))))
1 cặp bạn thân không thể có người thứ 3:))))))))
1 cặp bạn thì kiểu gì cũng có thg hai mặt :)))))))