Số lượng tam giác

Điểm: 20,00

Giới hạn thời gian: 1.0s

Giới hạn bộ nhớ: 256M

Input: stdin

Output: stdout

Tác giả:

minhquanz

Dạng bài

Ngôn ngữ cho phép

C, C++, Java, Kotlin, Output Only, Pascal, PyPy, Python

Cho dãy số ~a_1,a_2,..., a_n~. Hãy đếm xem có bao nhiêu cặp ~(i,j, k)~ mà ~ai, aj, ak~ tạo thành 3 cạnh của 1 tam giác.

Input Specification

Dòng đầu ghi số nguyên dương n là số lượng phần tử của dãy.
Dòng 2 ghi n số nguyên dương là dãy số ~a_1, a_2, ..., a_n~ ~(ai \leq 10^{9})~

Output Specification

In ra 1 số nguyên duy nhất là số lượng tam giác tạo được.

Sample Input

5
4 3 1 5 7

Sample Output

Bình luận

Hãy đọc nội quy trước khi bình luận.

-1

anhtuan2k12 đã bình luận lúc 10, Tháng 8, 2025, 11:03

include <iostream>

include <vector>

include <algorithm>

using namespace std;

int main() { int n; cin >> n; vector<long long> a(n); for (int i = 0; i < n; i++) cin >> a[i];

sort(a.begin(), a.end());

long long count = 0;
for (int k = n - 1; k >= 2; k--) {
    int i = 0, j = k - 1;
    while (i < j) {
        if (a[i] + a[j] > a[k]) {
            count += (j - i);
            j--;
        } else {
            i++;
        }
    }
}

cout << count << "\n";
return 0;

}