Cho một dãy N phần tử, năng lượng của dãy là tổng năng lượng của từng phần tử. Năng lượng của từng phần tử định nghĩa là tổng số lượng phần tử không lớn hơn chính nó (bao gồm cả nó).
Ví dụ dãy 1 1 2 3 số 1 đầu tiên có năng lượng là 2, số 1 tiếp theo có năng lượng là 2, số 2 có năng lượng là 3, số 3 có năng lượng là 4. Vì vậy đáp án sẽ là 2+2+3+4 = 11.
Đầu vào:
Dòng đầu chứa số lượng test case, dòng tiếp theo chứa giá trị N (1<=N <=50000), và N phần tử với giá trị mỗi phần tử k vượt quá 50000.
Đầu ra:
Mỗi dòng in năng lượng của cả dãy
Ví dụ dãy 1 1 2 3 số 1 đầu tiên có năng lượng là 2, số 1 tiếp theo có năng lượng là 2, số 2 có năng lượng là 3, số 3 có năng lượng là 4. Vì vậy đáp án sẽ là 2+2+3+4 = 11.
Đầu vào:
Dòng đầu chứa số lượng test case, dòng tiếp theo chứa giá trị N (1<=N <=50000), và N phần tử với giá trị mỗi phần tử k vượt quá 50000.
Đầu ra:
Mỗi dòng in năng lượng của cả dãy
Ví dụ
Lời giải:
Trong bài này các bạn sẽ làm quen với cách ánh xạ giá trị của từng phần tử, cách này sẽ giúp ta tính toán xem phần tử này lớn thứ bao nhiêu trong dãy.
Trong bài này các bạn sẽ làm quen với cách ánh xạ giá trị của từng phần tử, cách này sẽ giúp ta tính toán xem phần tử này lớn thứ bao nhiêu trong dãy.
Trong quá trình nhập mảng A[i] ta sẽ có một mảng tần suất F[], để đếm các giá trị của mảng A cũng như kiểm tra số lượng phần tử nhỏ hơn.
Ví dụ 1 1 2 3 thì ta sẽ có F[1] = 2, F[2] = 1, F[3] = 1 Sau đó duyệt từ giá trị 0 ta sẽ có năng lượng của 1 là 2, năng lượng của 2 là 3, năng lượng của 3 là 4. Các bạn tự cài đặt thuật toán. |
Chú ý là bài này tối đa sẽ có 50000 phần tử có giá trị 50000, vì vậy năng lượng là 2,5 tỉ vượt giới hạn của kiểu int.
Các bạn hãy chú ý kĩ thuật này, sẽ tối ưu rất nhiều trong quá trình kiểm tra tính trùng lặp. Mình sẽ giới thiệu trong các bài tiếp theo.
Các bạn hãy chú ý kĩ thuật này, sẽ tối ưu rất nhiều trong quá trình kiểm tra tính trùng lặp. Mình sẽ giới thiệu trong các bài tiếp theo.