Tổng Của Hiệu

Xem PDF
Tác giả:
shiba
Dạng bài
Ngôn ngữ cho phép
C++, Clang, Clang++, Cobol, D, Groovy, Haskell, JS, Lua, Node JS, ObjectiveC, Pascal, Prolog, Pypy, Pypy 3, Python, Scala
Điểm: 1100 (p) Thời gian: 1.0s Bộ nhớ: 256M Input: bàn phím Output: màn hình

Cho số nguyên dương \(N\) và dãy số có \(N\) số nguyên \(a_1,a_2,...,a_N\).

Yêu cầu: Bạn hãy in ra tổng của tất cả các giá trị \(∣a_i - a_j∣\) thỏa mãn \(1 \le i < j \le N\).

Input

  • Dòng đầu tiên chứa số nguyên dương \(N\) \((1 \le N \le 2 \times 10^5)\).
  • Dòng tiếp theo chứa dãy \(a_1,a_2,...,a_N\) \((-10^9 \le a_i \le 10^9)\), mỗi số cách nhau một khoảng trắng.

Output

  • In ra đáp án bài toán sau khi thực hiện yêu cầu đề bài.

Scoring

  • Subtask \(1\) (\(50\%\) số điểm): Có \(N \le 1000\).
  • Subtask \(2\) (\(50\%\) số điểm): Không có ràng buộc gì thêm.

Example

Test 1

Input 
3
5 1 2
Output 
8
Note

Ta có \(∣5-1∣ + ∣5-2∣ + ∣1-2∣ = 8\).

Bình luận


  • -20
    tungle0401    9:06 p.m. 7 Tháng 8, 2023

    Bình luận bị ẩn vì nhiều phản hồi tiêu cực. Nhấp vào đây để mở.

    1 phản hồi

    • 12
      LTKboy    11:10 p.m. 30 Tháng 5, 2023 ← chỉnh sửa 13

      Mình xin giải thích ý tưởng của bài này(nếu các bạn đọc không hiểu sol của anh \(Shiba\)):
      Đầu tiên, chúng ta sắp xếp lại dãy số a theo thứ tự không giảm. Sau đó, với mỗi phần tử \(a_i\), ta tính tổng của các giá trị \(|a_i - a_j|\) với \(j > i\). Tổng này được tính bằng công thức \((i+1) \times (n-i-1) \times (a_{i+1} - a_i)\). Giải thích công thức này như sau:

      • \((i+1)\) và \((n-i-1)\) là số lượng phần tử trong các nửa dãy bên trái và bên phải của \(a_i\).
      • \((a_{i+1} - a_i)\) là khoảng cách giữa \(a_i\) và phần tử lớn hơn nó nhất trong nửa dãy bên phải. Tổng này chính là tổng khoảng cách giữa các phần tử liên tiếp trong nửa dãy bên phải của \(a_i\).
        Cuối cùng, chúng ta cộng tổng các giá trị này lại để có được kết quả cuối cùng.
      Code C++

      Đây là code của bài này

      1 phản hồi