Cặp số bằng nhau
Xem dạng PDF
Gửi bài giải
Điểm:
0,01 (OI)
Giới hạn thời gian:
3.0s
Giới hạn bộ nhớ:
256M
Input:
CSBN.inp
Output:
CSBN.out
Tác giả:
Dạng bài
Ngôn ngữ cho phép
C, C++, Go, Java, Kotlin, Pascal, PyPy, Python, Rust, Scratch
Bình là học sinh có đam mê với các con số. Một hôm Bình ngồi viết ra 1 dãy số nguyên bất kì và nhận thấy có nhiều số nguyên có giá trị bằng nhau. Bình muốn biết dãy số vừa viết ra có bao nhiêu cặp số có giá trị bằng nhau nên nhờ các bạn học sinh giỏi Tin lập trình giúp.
Yêu cầu: Cho ~N~ số nguyên dương lần lượt là ~a_1~, ~a_2~, ..., ~a_N~. Hãy giúp Bình xác định có bao nhiêu cặp số bằng nhau (~a_i = a_j~ với ~i < j~ được tính là ~1~ cặp).
Input
Từ tệp văn bản CSBN.INP gồm ~2~ dòng:
Dòng thứ nhất là số nguyên ~N~ (~1 \le N \le 10^7~).
Dòng thứ hai gồm ~N~ số ~a_1~, ~a_2~, ..., ~a_N~ (~1 \le a_i \le 10^9~).
Output
Đưa tệp văn bản CSBN.OUT chứa số cặp bằng nhau.
Sample Input 1
5
4 5 4 6 1
Sample Output 1
1
Sample Input 2
7
7 8 6 8 6 3 6
Sample Output 2
4
Bình luận
include <bits/stdc++.h>
using namespace std; int upper(int n, int a[], int x) { int l = 1, r = n; int ans = -1; while(l <= r) { int mid = l + (r - l) / 2; if(a[mid] == x) {ans = mid; l = mid + 1;} else if(a[mid] < x) l = mid + 1; else r = mid - 1; } return ans; }
int lower(int n, int a[], int x) { int l = 1, r = n; int ans = -1; while(l <= r) { int mid = l + (r - l) / 2; if(a[mid] == x) {ans = mid; r = mid - 1;} else if(a[mid] > x) r = mid - 1; else l = mid + 1; } return ans; }
int main() { freopen("CSBN.INP", "r", stdin); freopen("CSBN.OUT", "w", stdout); iosbase :: syncwith_stdio(0); cin.tie(NULL); int n; cin >> n; int a[n + 9]; long long ans = 0; for(int i = 1; i <= n; i++) cin >> a[i]; sort(a + 1, a + 1 + n); for(int i = 1; i <= n; i++) { int l = lower(n, a, a[i]), r = upper(n, a, a[i]); long long abc = r - l + 1; ans += (abc * (abc - 1)) / 2; i = r + 1; } cout << ans; } // day la code tknp cho mn nhe
include<bits/stdc++.h>
using namespace std;
int main(){ freopen("CSBN.INP" , "r" , stdin); freopen("CSBN.OUT" , "w" , stdout); ios::syncwithstdio(false); cin.tie(NULL); cout.tie(NULL); int n; cin >> n; unorderedmap<int , int > mp; for(int i = 0 ; i < n ; i++){ int x ; cin >> x; mp[x]++; } int ans = 0; for(unorderedmap<int, int >::iterator it = mp.begin() ; it != mp.end() ; it++){ int count = it->second; ans+= count*(count-1)/2; } cout << ans; return 0; } // sao minh bi sai 10 test cuoi nhi
Bình luận này đã bị ẩn vì có quá nhiều phản ứng tiêu cực. Nhấn để xem.
Bình luận này đã bị ẩn vì có quá nhiều phản ứng tiêu cực. Nhấn để xem.
wtf cho hỏi:
dùng tknp sẽ an toàn hơn nếu dùng unordered_map trong thi thật khá rủi ro
nếu dùng tknp thì chỗ điều kiện i < j xử lí như nào vậy b
thì cặp giống nhau thì luôn có 1 chỉ số đứng trước mò:>>
Bài này dùng unordered_map sẽ không bị TLE 😊
Bình luận này đã bị ẩn vì có quá nhiều phản ứng tiêu cực. Nhấn để xem.
sos
Bình luận này đã bị ẩn vì có quá nhiều phản ứng tiêu cực. Nhấn để xem.
Bình luận này đã bị ẩn vì có quá nhiều phản ứng tiêu cực. Nhấn để xem.
Bình luận này đã bị ẩn vì có quá nhiều phản ứng tiêu cực. Nhấn để xem.
!SPOILER!
10^9 dùng map :))))))
Su dung unordered_map nhe, ban dung map chi qua duoc tam 10 test thoi