Giải bài ntucoder CASO - Cặp số

Link bài:

Cách 1:

Thuật toán:

• Ta dùng thuật toán sắp xếp dãy n số. Như vậy, các số giống nhau sẽ đứng cạnh nhau.
  
• Đến số lượng các số giống nhau bằng biến "dem", như vậy mỗi khi ai == ai-1, ta sẽ cộng dồn "dem".
  
• Một dãy con có "dem" số giống nhau thì số lượng các cặp sẽ là dem* (dem-1) /2

Code:

Mã:

#include <bits/stdc++.h>
using namespace std;

int a[100007], n;
long long int dem, ans;

void read(){
    ios_base::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
    //freopen("caso.inp", "r", stdin);
    //freopen("caso.out", "w", stdout);
    cin >> n;
    dem = 1;
    for (int i = 1; i <= n; i++) cin >> a;
}

void run(){
    sort(a+1, a+n+1);
    for (int i = 2; i <= n+1; i++){
        if (a == a[i-1]){
            dem++;
        }else{
            if (dem != 1){
                ans += dem*(dem-1)/2;
                dem = 1;
            }
        }
    }

    cout << ans;
}

int main(){
    read();
    run();

    return 0;
}

Cách 2:
Thuật toán:

• Thay vì dùng mảng a để chứa các phần tử, ta sẽ dùng nó để chứa số lần xuất hiện của các phần tử (Vì các phần tử không lớn hơn 1e5 nên kích thước mảng so với cách 1 là không đổi).
• Ta sắp xếp mảng để đưa các số phần tử về đầu mảng nhằm tiện lợi hơn khi tính.
• Cộng dồn số cặp dựa trên số lần xuất hiện của các phần tử bằng công thức ai*(ai-1).

Code:

Mã:

#include <bits/stdc++.h>
using namespace std;

long long int ans, a[100007];
int n, x;


int main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
    //freopen("caso.inp", "r", stdin);
    //freopen("caso.out", "w", stdout);
    cin >> n;
    for (int i = 1; i <= n; i++) {cin >> x; a[x]++;}
    sort(a+1, a+100000+1, greater<int>());
 
    for (int i = 1; i <= 100000; i++) if (a == 0) break; else
        if (a > 1) ans += a*(a - 1)/2;
    cout << ans;
 
    return 0;
}