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


  • 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


    • -10
      PY2GCaoVanAnhKiet    9:38 a.m. 14 Tháng 7, 2023

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


      • 6
        Choker    3:46 p.m. 14 Tháng 7, 2023

        Mới học mà sao làm được bài này hay vậy ?


        • -11
          PY2GCaoVanAnhKiet    7:55 p.m. 17 Tháng 7, 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
            dangluu2013    9:34 p.m. 25 Tháng 4, 2024

            rảnh tự dưng khai
            muốn thầy Small nói:"Con acc này đã bị bannnnnnnnnnnnnnnn"
            và teo teo teo tèo téo teo :(((((((((((nooooooooooo


            • 0
              hoangnguyenkhoa    6:01 p.m. 5 Tháng 4, 2024

              hết cứu 🙂


              • 1
                PY2GTranNguyenAnhKhoi    8:34 p.m. 15 Tháng 9, 2023

                chưa ban à :))


                • 6
                  kovaodcLQD2025    9:26 a.m. 5 Tháng 8, 2023

                  Hết cứu =))))


                  • 4
                    NguyenLePhuc    10:36 a.m. 29 Tháng 7, 2023

                    muốn ban acc hay sao vậy?


                    • 4
                      ngvanminh_    10:04 p.m. 18 Tháng 7, 2023

                      tự hủy cực mạnh:)


                      • 4
                        Choker    8:25 p.m. 18 Tháng 7, 2023

                        Báo thầy Nhỏ nhỉ ? =)))

                  1 bình luận nữa