Số cặp
Xem PDF
Điểm:
100 (p)
Thời gian:
1.0s
Bộ nhớ:
256M
Input:
bàn phím
Output:
màn hình
Cho một mảng gồm \(n\) số nguyên dương \(a_1,\) \(a_2,\) \(a_3,\) \(...,\) \(a_n.\)
Yêu cầu : Hỏi có bao nhiêu cặp số bằng nhau ? \((\)Bao nhiêu cặp \(a_i\) \(=\) \(a_j\) với \(i\) \(\neq\) \(j,\) \((ai,\) \(aj)\) và \((aj,\) \(ai)\) chỉ được tính là \(1\) cặp\().\)
Input
- Dòng thứ nhất là chiều dài \(n\) của mảng \((1\) \(\leq\) \(n\) \(\leq\) \(10^5).\)
- Dòng thứ hai gồm \(n\) số nguyên \(a_1,\) \(a_2,\) \(a_3,\) \(...,\) \(a_n\) \((1\) \(\leq\) \(a_i\) \(\leq\) \(10^5),\) mỗi số cách nhau một khoảng trắng.
Output
- Là số nguyên xác định số lượng các cặp bằng nhau.
Example
Test 1
Input
5
8 2 9 8 1Output
1Test 2
Input
7
6 2 4 2 4 3 4Output
4
Bình luận
bài này có thể dùng map với độ phức tạp O(n)
code mẫu
include<bits/stdc++.h>
define ll long long
using namespace std;
int main()
{
ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
ll n;
cin>>n;
ll t=0,m;
map<ll,ll> a;
for(ll i=0;i<n;i++) { cin>>m;
a.insert(make_pair(m,1));
if(a.size()==t)
{
a[m]++;
}
else t++;
}
ll dem=0;
for(pair<ll,ll> i:a)
{
if(i.second!=1)
{
i.second--;
dem+=(i.second+1)*i.second/2;
}
}
cout<<dem;
}
11 bình luận nữa