Lễ hội

Xem dạng PDF
Gửi bài giải
Điểm: 0,78 (OI)
Giới hạn thời gian: 1.0s
Giới hạn bộ nhớ: 256M
Input: stdin
Output: stdout
Tác giả:
FireGhost130104
Dạng bài
Ngôn ngữ cho phép
C, C++, Go, Java, Kotlin, Pascal, PyPy, Python, Rust, Scratch

Ở ngôi làng nọ, có ~n~ ngôi nhà nằm trên một đường thẳng. Biết trưởng làng sống ở nhà thứ ~1~, nhà thứ ~i~ nằm cách nhà trưởng làng đúng ~a_i~ km về phía đông.

Sắp tới mùa Tết, trưởng làng muốn chọn ra một số địa điểm trên đường thẳng để chuẩn bị tổ chức hội hoa xuân. Chi phí để chuẩn bị một hội hoa xuân là ~k~ coin.

Sau khi chuẩn bị xong, tất cả người dân sẽ di chuyển đến hội hoa xuân gần nhà mình nhất để tham gia. Nếu một người dân ở cách địa điểm ~x~ km, chi phí để di chuyển sẽ là ~x~ coin.

Hãy tìm cách chọn một số địa điểm sao cho tổng chi phí tổ chức lễ hội và di chuyển là nhỏ nhất.

Nói cách khác, nếu như ta chọn ~m~ địa điểm, địa điểm thứ ~i~ nằm cách nhà trưởng làng đúng ~s_i~ km về phía đông, tổng chi phí tổ chức lễ hội và di chuyển sẽ là ~k \cdot m + \sum \limits_{i = 1}^{n} \min \limits_{j = 1}^{m} |a_i - s_j|~.

Input

Dòng đầu tiên chứa hai số nguyên dương ~n~ (~1 \le n \le 2 \cdot 10^5~) — số ngôi nhà trong làng và ~k~ (~1 \le k \le 10^9~) — chi phí tổ chức một hội hoa xuân.

Dòng tiếp theo chứa ~n~ số nguyên dương ~a_1, a_2, \ldots, a_n~ (~0 = a_1 < a_2 < \ldots < a_n \le 10^9~), trong đó ~a_i~ thể hiện khoảng cách từ nhà thứ ~1~ đến nhà thứ ~i~.

Output

Một dòng duy nhất chứa đáp án của bài toán: tổng chi phí tổ chức lễ hội và di chuyển nhỏ nhất.

Sample Input 1

4 5
0 1 6 10

Sample Output 1

15

Notes

Ở test mẫu, ta có thể tổ chức lễ hội tại các địa điểm ~1~ và ~9~.

Khi đó, người dân ở nhà ~1~ và ~2~ sẽ di chuyển tới địa điểm thứ nhất, người dân ở nhà ~3~ và ~4~ sẽ di chuyển tới địa điểm thứ hai.

Tổng chi phí tổ chức lễ hội và di chuyển sẽ là ~2 \cdot 5 + |0 - 1| + |1 - 1| + |6 - 9| + |10 - 9| = 15~.

Bình luận

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


  • 13
    TranThienPhuc2657  đã bình luận lúc 7, Tháng 7, 2026, 12:41 ← sửa 4

    Comment này spoil thuật

    Comment này gồm hai phần, do là giới hạn comment của VNOJ chỉ có 8192 kí tự. Phần 2 các bạn có thể kéo xuống dưới phần reply comment của mình để đọc nhé!

    Các bạn thấy hay và bổ ích thì cho tui xin hai upvote cho hai phần của comment nhé, tui xin cảm ơn!

    Đây là phần 1 của comment

    Các thông tin cơ bản, lưu ý trước khi đọc bài viết này

    Giới thiệu:

    • Người viết: Trần Thiên Phúc

    • Trường: Học sinh mới ra trường THPT Chuyên Hùng Vương, đã từng học lớp Chuyên Tin của trường trong 3 năm, niên khóa: 2023 - 2026.

    Bài viết này được viết và cả gõ ~\rm LaTeX~ hoàn toàn bằng tay trong vòng hơn 3 tiếng đồng hồ.

    Tui chỉ là làm bài xong thấy bài hay quá nên là tui tiện viết solution để tui nhớ và hiểu thật sự và để cho mọi người cũng học hỏi.

    Nên là nếu các bạn không thích điều gì ở solution này thì có thể comment ở dưới để mình sửa đổi cho hoàn thiện hơn. Tui xin cảm ơn!!!

    Bài viết này mình viết theo mạch suy nghĩ của bản thân, cho nên là sẽ có những bước nằm sau nó có thể là tiền đề cho bước nằm trước nhưng mà tới mãi lúc sau minh mới nghĩ tới

    Các code mẫu chỉ để mục đích tham khảo cách cài đặt, mong các bạn không sao chép chỉ để cho nó AC, điều đó không có ý nghĩa gì cả.

    Các lưu ý về kí hiệu

    1) ~a_i~ và ~a[i]~ là một, mình kí hiệu khác nhau tùy thuộc vào độ phức tạp của công thức để cho nó dễ nhìn nhất có thể

    2) ~\rm opt~ để chỉ mảng ~\mathrm{opt}[]~, ~opt~ để chỉ biến ~opt~

    Subtask 1

    Thuật toán ~\mathcal O(n^2)~

    Để giải được bài này, trước tiên cần phải làm được subtask con trước, ở đây là ~\mathcal O(n^2)~ (tuy là đề bài không có chia sẵn nhưng mà việc chia ra giải để mà có hướng cải tiến)

    Nhận xét 1

    Đây là một nhận xét về toán học và mình cũng không biết chứng minh, mình có biết từ trước sau khi đọc lời giải của một bài VNOI Cup mình từng làm: Hai Mảng

    Cho biểu thức: $$\min \sum_{i = 1}^n |a[i] - X|$$ Biểu thức này xảy ra khi ~X~ là một số trong đoạn chứa trung vị của dãy số.

    Hay nói cách khác: $$ \sum_{i = 1}^n |a[i] - X| = \min \implies \begin{cases} X = a_{(n + 1) / 2} & n \% 2 = 0 \\ X \in \left[ a_{n / 2}; a_{n / 2 + 1} \right] & n \% 2 = 1 \end{cases} $$

    Ý tưởng

    Ta có thể tưởng tượng về bài toán chia đoạn: Cho ~n~ số và chia thành các đoạn, mỗi đoạn có giá trị là $$\mathrm{cost}(l, r) = \sum_{i = l}^r |a[i] - \mathrm{med}(a[l \dots r])| + k$$ Với ~\mathrm{med}(a[l \dots r])~ là trung vị của đoạn ~a[l], a[l + 1], \dots, a[r]~

    Cộng thêm ~k~ là do mỗi đoạn tăng thêm phải có thêm chi phí thêm là ~k~

    Cách mình nghĩ ra ý tưởng

    Có phần tà đạo là mình biết trước tag của bài này cho nên là mình mới nghĩ ra được ý tưởng này, nhưng mà thường thì do cảm giác là có hàm tính ~\rm cost~ của một đoạn thì sẽ chia đoạn ra.

    Công thức chi tiết tính hàm ~\mathrm{cost}(l, r)~:

    Phân tích ra thêm thì ta có thể tính nhanh giá trị này khi chuẩn bị sẵn prefix sum từ trước

    Gọi: ~\displaystyle mid = \left \lfloor \frac{l + r} 2 \right \rfloor~, ~\displaystyle \mathrm{pref}[i] = \sum_{j = 1}^i a[j]~: mảng tiền tố (prefix sum) cho tới vị trí ~i~

    Với phép trị tuyệt đối ~|a[i] - X|~, ta phá trị tuyệt đối thành hai trường hợp sau: $$|a[i] - X| = \begin{cases} X - a[i] & a[i] \le X \\ a[i] - X & a[i] > X \end{cases}$$

    Lấy trung vị của đoạn tại: ~a[mid]~

    Trong trường hợp này, với mảng đã xác định sẵn nên ta có thể xác định rõ: $$\begin{cases} a[i] \le a[mid] \implies i \le mid \\ a[i] > a[mid] \implies i > mid \end{cases}$$

    Khi này công thức sẽ là: $$\mathrm{cost}(l, r) = \sum_{i = l}^r |a[i] - \mathrm{med}(a[l \dots r])| + k$$

    $$= \sum_{i = l}^{mid} a[mid] - a[i] + \sum_{i = mid + 1}^r a[i] - a[mid]$$

    $$= (mid - l + 1) \cdot a[mid] - (\mathrm{pref}[mid] - \mathrm{pref}[l - 1]) + (\mathrm{pref}[r] - \mathrm{pref}[mid]) - (r - (mid + 1) + 1) \cdot a[mid]$$

    Gọi ~\mathrm{dp}[i]~: chi phí tối ưu để mà chọn đoạn cho tới vị trí ~i~

    Công thức tính: $$dp[i] = \min(dp[j] + \mathrm{cost}(j + 1, i)), \quad j \in [1; i - 1]$$

    Độ phức tạp: ~\mathcal O(n^2)~

    Nhận xét 2

    Giải thích này dùng để giải thích cho tính đúng đắn của thuật toán

    Cách tui nghĩ ra nhận xét và giải thích các nhận xét

    1) Trong lúc làm bài, mình có nghĩ tới trường hợp: Giả sử có một trường hợp nào đó mà với hai đoạn liên tiếp, phần tử đầu của đoạn hai lại gần trung vị của đoạn đầu hơn so với đoạn hiện tại của nó. Khi này thì công thức sẽ không tính đúng nữa.

    Để mà dễ hình dung điều tui sắp nói, bạn có thể vẽ ra hai tập điểm gồm các điểm nằm gần nhau và khoảng cách giữa hai tập điểm đó xa nhau.

    Khi này thì cái phần tử đó nó có vẻ "gần" đoạn đầu và "xa" đoạn sau

    Khi xét tới trường hợp mà đoạn đầu thu nạp phần tử đó:

    • Chính phần tử đó: khi này do là phần tử đó gần đoạn đầu hơn nên là khoảng cách nó sẽ tối ưu hơn so với cách ở trên.
    • Các cái phần tử ở đoạn sau: do là bị loại bỏ phần tử xa đi rồi nên trung vị sẽ gần các phần tử đó hơn dẫn tới tổng giá trị khoảng cách của đoạn sau nó cũng sẽ tối ưu hơn.
    • Các giá trị ở đoạn trước: khi thêm phần tử thì tổng giá trị khoảng cách sẽ có tăng lên nhưng mà dễ dàng nhận thấy thì lượng tăng của nó nó không đáng kể so với lượng giảm đi

    ~\implies~ Điều này giúp mình nhận ra rằng mình cũng chẳng cần quan tâm tới việc cái công thức nó chia đoạn và tính giá trị không đúng, tại vì nếu nó chia không đúng thì sẽ có cách chia đúng nó sẽ luôn tối ưu lên.

    2) Mình cũng nhận ra là đáp án cuối cùng cũng là một cách chia đoạn tối ưu nhất thỏa mãn cách tính của hàm quy hoạch động đã định nghĩa.

    Tại vì sẽ không có trường hợp nào mà điểm 1 gần trung vị 1 ở bên trái, điểm 2 gần trung vị 2 ở bên phải mà đáp án cuối cùng lại ghép cặp: (1, TV2), (2, TV1) cả. Nó hoàn toàn không hợp lệ.

    ~\implies~ Cho nên là đáp án cuối cùng luôn là một đáp án thỏa mãn cách tính quy hoạch động như trên.

    Nhận xét: Không cần quan tâm tới việc cái công thức nó chia đoạn và tính giá trị không đúng, tại vì nếu nó chia không đúng thì sẽ có cách chia đúng nó sẽ luôn tối ưu lên và đáp án cuối cùng là một cách chia đoạn tối ưu nhất thỏa mãn cách tính của hàm quy hoạch động đã định nghĩa.

    Nhờ vậy, ta có thể thấy được, cho dù quá trình tính có vẻ hơi sai sai nhưng mà kết quả cho ra cuối cùng là kết quả đúng.


    • 1
      baohan2000  đã bình luận lúc 7, Tháng 7, 2026, 14:35

      dạ a giải hay quá ạ !!! ^-^


    • 1
      LMT_DN  đã bình luận lúc 7, Tháng 7, 2026, 13:21

      orz tranthienphuc


    • 1
      BuiDinhLoc  đã bình luận lúc 7, Tháng 7, 2026, 13:03

      Mình không ngờ có thể suy nghĩ như vậy luôn :O

      Cảm ơn bạn nhé!


    • 2
      duchohoang1801  đã bình luận lúc 7, Tháng 7, 2026, 13:01

      Hay quá ạ =0


    • 3
      TgX_2  đã bình luận lúc 7, Tháng 7, 2026, 12:57

      à hóa ra là vậy


    • 12
      TranThienPhuc2657  đã bình luận lúc 7, Tháng 7, 2026, 12:41 ← sửa 7

      Đây là phần 2 của comment

      Subtask full

      Thuật toán ~\mathcal O(n \log n)~

      Nhận xét 3:

      Gọi ~\mathrm{opt}[i]~: vị trí khiến cho ~\mathrm{dp}[i]~ tối ưu. Hay nói cách khác: $$\mathrm{dp}[i] = \mathrm{dp}[\mathrm{opt}[i]] + \mathrm{cost} \implies \mathrm{dp}[i] = \min$$

      Sau khi hoàn thành tính toán ở subtask 1 thì in cái mảng ~\mathrm{opt}~ ra quan sát, thấy được:

      $$\mathrm{opt}[1] \le \mathrm{opt}[2] \le \cdots \le \mathrm{opt}[n]$$

      ~\implies~ Đây là một dấu hiệu cho thấy là bài này có thể sử dụng kĩ thuật DP DNC hoặc có thể sử dụng DNC Chen Danqi hay Deque trên mảng tịnh tiến để giảm độ phức tạp từ ~\mathcal O(n^2)~ xuống ~\mathcal O(n \log n)~

      Cách cài đặt 1: Thuần DP DNC

      Đọc trước: DP DNC

      Nếu như mà trong DP DNC thì ban đầu sẽ tính đáp án cho ~\mathrm{dp}[mid]~ trước luôn để ra được ~opt~ nhưng mà ở đây thì là do các cái trạng trước chưa được tính trước cho nên là không làm vậy được.

      Thay vì thế thì ta có thể:

      1) DNC cho vế trái trước với ~optl = optl, optr = optr~.

      2) Sau đó tính ~\mathrm{dp}[mid]~ sau rồi thì có ~opt~

      3) DNC vế phải với biến ~opt~ như DP DNC bình thường

      Độ phức tạp: ~\mathcal O(n \log n)~.

      Tuy vậy thì do là vế trái không có chặn cận cho nên là nó sẽ bị chậm hơn chút.

      Thực tế code theo cách này của mình chạy được ~0.57 \rm s~

      Cách cài đặt 2: DNC Chen Danqi + DP DNC

      Đọc trước: DP DNC, DNC Chen Danqi

      Nguồn tham khảo: Code của ITK14_GiaBao: Code, nếu đã AC rồi thì có thể vào xem

      Khác với cách cài đặt 1 thì lần này, do là đặc tính trạng thái sau phải tính từ các cái trạng thái trước, ta có thể áp dụng DNC Chen Danqi và sử dụng hàm DP DNC bình thường với các bước như sau:

      1) Tính nửa trái trước

      2) Tính đáp án nửa phải nhưng chỉ có lấy từ các đáp án của nửa trái để tối ưu

      3) Tính tiếp nửa phải nhưng chỉ có lấy các đáp án trong nửa phải để tối ưu.

      Khi này thì nửa phải do là đã được tối ưu từ nửa trái rồi nên không còn dính dáng tới nửa trái nữa nên nó trở thành một bài toán độc lập.

      Giải thích tại sao DP Chen Danqi có thể áp dụng vào được bài toán này và tại sao chỉ cần sử dụng hàm DP DNC bình thường.

      Thường DP Chen Danqi được sử dụng khi các trạng thái chưa được tính trước mà chỉ có một cái base case, việc đệ quy tính trái trước liên tục xuống đáy sẽ xuống tới base case. Khi mà tới base case rồi thì không cần tính nữa.

      Khi này, ở tầng dưới cùng, 0 có thể truyền được cho 1 do đã tính trước rồi. Khi nâng tầng lên thì luôn đảm bảo là các ~\rm dp~ ở bên trái đã được tính sẵn rồi. Do đó luôn có thể truyền từ trái sang phải.

      Đồng thời ta có thể sử dụng hàm dnc bình thường (tính ~\mathrm{dp}[mid]~ trước rồi dnc xuống hai bên sau) để mà tính do là lúc mà gọi hàm dnc thì luôn tính trước các trạng thái bên trái xong rồi.

      Độ phức tạp: ~\mathcal O(n \log n)~

      Nhưng mà sẽ nhanh hơn cách cài đặt 1 do là mình dùng hàm dnc bình thường nên đảm bảo là hàm phiên bản tối ưu nhất chứ không phải là kém tối ưu hơn chút như cách trên.

      Thực tế code theo cách này của mình chạy được ~0.2 \rm s~

      Cách cài đặt 3: 1D1D optimization (Deque trên mảng tịnh tiến)

      Đọc trước: 1D1D optimization, cảm ơn davele đã cho tui biết tên thuật

      Nguồn tham khảo: Code của Zero_OP: Code, nếu đã AC rồi thì có thể vào xem.

      Ta có thể sử dụng tính chất ~\rm opt~ tăng dần để có thể cài đặt deque (gọi là ~\mathtt{dq}~) như sau:

      1) Lưu bộ ba thông tin: ~\{ l, r, opt \}~: ~opt~ tối ưu cho các phần tử đoạn ~[l; r]~

      2) ~\mathtt{dq.front()}~ lưu thông tin ~opt~ cho vị trí ~i~ hiện tại đang xét

      3) Các cái phần tử trong deque được sắp xếp theo phần tử sau có đoạn ~[l; r]~ nằm sau phẩn tử trước, đồng thời ~opt~ tăng dần.

      Cách hoạt động:

      1) Ban đầu bỏ vào trạng thái ~\{ 1, n, 0 \}~ vào: phần tử vị trí ~0~ đang tối ưu cho toàn mảng, về sau bỏ mấy cái khác tối ưu hơn rồi sẽ sửa lại sau.

      2) Duyệt từng phần tử vị trí ~i~ từ ~1~ tới ~n~

      3) Tính đáp án ~\mathrm{dp}[i]~ dựa trên ~opt~ của ~\mathtt{dq.front()}~

      4) Bây giờ ~i~ cũng có thể trở thành ~opt~ của một đoạn nào đó, ta khử các phần tử ~\mathtt{dq.back()}~ mà tại đó ~\mathtt{dq.back()}.opt~ không còn tối ưu tại vị trí ~\mathtt{dq.back()}.l~ được bằng ~i~ nữa.

      Giải thích lí do

      Do là nếu tại ~\mathtt{dq.back()}.l~ đã không tối ưu rồi thì các phần tử sau nó cũng sẽ không tối ưu nữa do là mảng ~opt~ có tính tăng dần, một khi cái trước đã là ~i~ rồi thì các cái ~opt~ sau không thể nhỏ hơn ~i~ được.

      5) Khi mà không còn khử ra được nữa, có hai trường hợp

      5.1) Deque rỗng: Khi này ta thêm vào deque: ~\{i + 1, n, i \}~. Do là tới lúc này thì ~i~ đang tối ưu cho toàn mảng phía sau

      5.2) Còn phần tử phía sau.

      Khi này thì tại vị trí ~\mathtt{dq.back()}.l~ thì cái ~\mathtt{dq.back()}.opt~ nó tối ưu hơn nhưng không có nghĩa là nó sẽ tối ưu trên toàn đoạn ~[\mathtt{dq.back()}.l; \mathtt{dq.back()}.r]~ như trước nữa.

      Khi này ta chặt nhị phân để tìm ra vị trí nào mà ~i~ bắt đầu chiếm ưu thế trên đoạn đó so với ~\mathtt{dq.back()}.opt~.

      • Nếu mà không có thì ta không thêm

      • Còn nếu có thì (gọi vị trí đó là ~x~)

        • Ta sẽ thay đổi thông tin ~\mathtt{dq.back()}.r = x - 1~
        • Thêm một đoạn mới vào ~\mathtt{dq.back()}~ là ~\{ x + 1, n, i \}~ (Do mình ưu tiên đoạn có ~[l; r]~ ở trước lên trước nên đoạn này mình để ở sau)
      Độ phức tạp: ~\mathcal O(n \log n)~

      Deque ~\mathcal O(n)~ ~\times~ Chặt nhị phân ~\mathcal O(\log n) = \mathcal O(n \log n)~

      (Tui không rõ phần này cho lắm nên tui sẽ giải thích theo cách hiểu của tui) Theo tui thấy đây là cách nhanh nhất trong ba cách là tại nó không dùng đệ quy nên nó sẽ giảm đi cái hằng số gọi hàm đệ quy.

      Thực tế code theo cách này của mình chạy được ~0.04 \rm s~

      Code mẫu

      Các code mẫu chỉ để mục đích tham khảo cách cài đặt, mong các bạn không sao chép chỉ để cho nó AC, điều đó không có ý nghĩa gì cả.

      Subtask 1

      Subtask 1, đã kèm mảng opt của nhận xét 3

      Subtask 2

      Subtask 2, cách cài đặt 1: Thuần DP DNC

      Subtask 2, cách cài đặt 2: DNC Chen Danqi + DP DNC

      Subtask 2, cách cài đặt 3: 1D1D optimization


      • 2
        davele  đã bình luận lúc 10, Tháng 7, 2026, 2:04 ← chỉnh sửa

        Cách 3 còn có tên gọi khác là 1D1D Optimization nhé. Xem thêm tại https://wiki.vnoi.info/vnoi-magazine/2023/1d1d-dp-optimization


      • 2
        ᅠᅠᅠ  đã bình luận lúc 7, Tháng 7, 2026, 12:59

        Cảm ơn bạn nhé, mình đang vướng mắc bài này


  • -8
    buivietthanh  đã bình luận lúc 6, Tháng 12, 2023, 1:35 ← chỉnh sửa

    Bình luận này đã bị ẩn vì có quá nhiều phản ứng tiêu cực. Nhấn để xem.