Tổng Của Hiệu

Xem PDF
Tất cả bài nộp
Các bài nộp tốt nhất
Xem hướng dẫn
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


  • 13
    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


    • -19
      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ở.


      • 5
        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 ?


        • -23
          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ở.


          • 2
            kietlqt    2:52 p.m. 1 Tháng 6, 2024

            Bro tôi nghĩ bạn sắp bị ban đấy


            • -1
              scratch_huykhanh    9:10 a.m. 8 Tháng 9, 2024

              nhìn lại mik cx chả khác j nó mà phán như thật :))


              • 1
                minhlaiha0    9:50 p.m. 4 Tháng 7, 2024

                đúng thế, bạn sẽ bị ban đấy kiệt


            • 1
              dxuhai    2:17 p.m. 12 Tháng 5, 2024

              Bro à, tôi xin thông báo vì bạn đã hết cứu:))


              • 2
                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


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

                hết cứu 🙂


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

                  chưa ban à :))


                  • 7
                    Alya    9:26 a.m. 5 Tháng 8, 2023

                    Hết cứu =))))


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

                      muốn ban acc hay sao vậy?


                      • 6
                        Shirokito    10:04 p.m. 18 Tháng 7, 2023

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


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

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

                  1 bình luận nữa