SCBN2 - Số cặp bằng nhau 2
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
Tác giả:
Dạng bài
Ngôn ngữ cho phép
C, C#, C++, Go, Java, Pascal, Perl, PHP, Python, Ruby, Rust, Scratch, Swift
Cho một dãy gồm ~n~ số nguyên, hãy đếm số cặp bằng nhau trong dãy
Input
- Dòng đầu tiên chứa duy nhất một số nguyên dương ~n~ (số phần tử trong dãy).
- Dòng thứ hai chứa n số nguyên là các phần tử ~a_1,a_2,…,a_n~
Giới hạn:
- ~1≤n≤10^5,0≤a_i≤5.10^4~
Output
- In ra trên một dòng số nguyên không âm là số cặp bằng nhau liên tiếp trong dãy.
Sample
Input #1
4
3 1 2 3
Output #1
1
Input #2
5
4 1 1 2 2
Output #2
2
Input #3
6
5 3 1 2 1 1
Output #3
3
Problem source: Chuyên Sơn La Online Judge
Bình luận
include <bits/stdc++.h>
using namespace std; long long a[100005]; long long n; long long dem=1; long long ketqua=0; int main() { cin>>n; for(int i=1;i<=n;i++) { cin>>a[i]; } sort(a+1,a+n+1); a[n+1]=a[n]+1; for(int i=1;i<=n;i++) { if(a[i]==a[i+1]) { dem++; } else { ketqua+=dem*(dem-1)/2; dem=1; } } cout<<ketqua; return 0; } ae xem ok ko:))
Ý tưởng giải bài này: Thay vì dùng long long int thì dùng string đi vì string không có giới hạn
Bình luận này đã bị ẩn vì có quá nhiều phản ứng tiêu cực. Nhấn để xem.
đề bịp :v có test long long mà bảo a[i] <= 5e4
O(n^2) =))
test 7 là gì thế ạ
bài này bạn có thể sử dụng map để lưu tần suất xuất hiện của các phần tử trong mảng, xong bạn check nếu số lần xuất hiện lớn hơn 2 thì bạn tính tổ hợp chập 2
Bình luận này đã bị ẩn vì có quá nhiều phản ứng tiêu cực. Nhấn để xem.
ban dua minh day a. So luong cap la to hop chap 2 cua k phan tu voi k te nhat bang n.Int chua bang mat
Bài này mng làm cách nào vậy ạ?? E làm mãi k ac được :((
bài này bạn có thể sử dụng map hoặc mảng đếm để lưu tần suất xuất hiện rồi ktra nếu xuất hiện từ 2 lần trở lên thì bạn tính tổ hợp chập 2
tôi có dùng rồi nhưng tính giai thừa cũng bị tle
Bạn tham khảo ý tưởng giải bài : link enter link description here