Bedao Regular Contest 20 - Đá thủ

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

HuyAT là học sinh trường P giấu tên mới thi kỳ thi V giấu tên. Vì cay cú khi choke, anh ấy đã chơi một trò để tịnh tâm lại. Trò chơi được mô tả như sau.

Ban đầu có ~N~ chồng đá, chồng thứ ~i~ có ~A_i~ viên đá. Ở mỗi lượt đi, HuyAT có thể mua ~1~ viên đá giá ~C_1~ hoặc ~2~ viên đá với giá ~C_2~. Sau khi mua đá xong thì HuyAT sẽ đặt những viên đá mình mua vòng các chồng đá. Ở mỗi lượt, mỗi chồng đá chỉ được đặt đá vào tối đa một lần. Trò chơi kết thúc khi mọi chồng đá có cùng độ cao.

Vì tiếc tiền, HuyAT muốn dùng ít tiền nhất để hoàn thành trò chơi. Hãy giúp HuyAT nhé.

Input

  • Dòng đầu tiên gồm ba số nguyên ~N, C_1, C_2~ ~(1 \le N \le 10^5, 1 \le C_1, C_2 \le 10^5)~.

  • Dòng thứ hai gồm ~N~ số nguyên là mảng ~A~ ~(1 \le A_i \le 10^6)~.

Output

  • In ra một số nguyên là số tiền tối thiểu để hoàn thành trò chơi.

Scoring

Subtask Điểm Giới hạn
~1~ ~20\%~ ~C_1 \times 2 \le C_2~
~2~ ~20\%~ ~C_1\le C_2~
~3~ ~30\%~ ~N\le 1000, A_i\le 1000~
~4~ ~30\%~ Không có ràng buộc gì thêm

Sample Input 1

2 15 3
1 4

Sample Output 1

45

Sample Input 2

5 10 4
2 11 11 11 12

Sample Output 2

54

Notes

Giải thích test ví dụ:

  • Ở test đầu tiên, ta mua ~3~ viên đá ở ~3~ lượt và đều đặt chúng vào chồng thứ nhất.

Bình luận

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


  • 1
    Thien2009  đã bình luận lúc 12, Tháng 6, 2026, 3:55 ← sửa 2

    Xin chào

    Mình xin phép đóng góp 1 lời giải bằng tìm kiếm nhị phân

    Trước tiên chúng ta định nghĩa:

    ~Max~ là độ cao của cột đá cao nhất

    ~Min~ là độ cao của cột đá thấp nhất

    ~cnt~ là tổng độ cao của các cột đá

    ~ans~ là đáp án cần tìm

    Sub 1:

    ~c_1 \times 2 \le c_2~

    Thì chúng ta luôn có thể chọn ~c_1~ để đạt giá trị nhỏ nhất

    ~\implies ans = (Max \times n) - cnt~

    ~\mathcal O(n)~

    Sub 2 :

    ~c_1 \le c_2~

    Ta chọn cách tham lam, chúng ta có thể chọn phân phố đều cho các cột đá

    Luôn ưu tiên phân phố cho cột có độ cao bé nhất và cột có độ cao bé nhì

    Chúng ta luôn có thể chọn cách phân phối để tới 1 thời điểm nào đó có nhiều nhất 1 cột đa có độ cao ~\le Max~

    Dễ thấy lúc này ta chọn ~c_2~ thì chắc chắn ~ans~ sẽ tệ đi

    Nếu như ~Min~ quá nhỏ, thì ta mỗi lượt bỏ 1 viên đá vào cột Min và 1 viên khác vào cột bất kì

    ~\mathcal O(n)~

    Sub 3:

    Mở rộng từ sub 2, lúc này,

    Ta không biết được ~c_2~ có làm đáp án tệ đi không nên ta phải giớ hạn độ cao của các cột

    Tham lam như sub 2 với từng độ cao giới hạn ~h~ , ~Max \le h \le 2 \times Max~

    Trường hợp tệ nhất : ~\{0, 1000, 1000\} \rightarrow \{2000, 2000, 2000\}~

    ~\mathcal O(Max \times n)~

    Sub 4:

    Mở rộng từ sub 3,

    Gọi ~\mathtt{sum}(h)~ là số bước tối thiểu để mọi chòng đá có độ cao ~h~

    ~Max \le h \le 2 \times Max~

    Nếu tất cả các cột đá đã có độ cao ~h~ thì ta chỉ cần thêm đá theo chu kì

    ~\implies~ Ta luôn có ~\mathtt{sum}(h) \ge \mathtt{sum}(h + 2) + c_2 \times n~

    Trường hợp đặc biệt là ~n = 1~ thì ~ans~ luôn ~= 0~

    Mỗi lần ~h~ tăng lên thì ta có nhiều cách sắp xếp hơn

    ~\implies~ Hàm ~\mathtt{sum}(h)~ sẽ có dạng là được parabol hướng lên

    ~\implies~ Ta chỉ cần tìm đỉnh của parabol bằng chặt nhị phân

    • Lưu ý: Hàm ~\mathtt{sum}(h)~ chỉ thể hiện đường parabol với các ~h~ có cùng tính chẵn lẻ

    • ~n = 5, c_1 = 10^9, c_2 = 1 \implies \mathtt{sum}(1) = 10^5 + 2, \mathtt{sum}(2) = 5~

    Đây là các test nhỏ mà bạn có thể tự kiểm tra

    Input:

    4 3 4
3 5 3 3

    Output:

    12

    Input:

    3 3 1
5 5 1

    Output:

    8

    Input:

    5 4 4
1 5 5 1 1

    Output:

    24

    Input:

    1 3 1
2

    Output:

    0

  • 1
    Thien2009  đã bình luận lúc 11, Tháng 6, 2026, 4:41

    Dạ mọi người ơi cho em hỏi là bài này dùng long long thôi được không ạ chứ em thấy giớ hạn hơi lơn


    • 1
      TranThienPhuc2657  đã bình luận lúc 12, Tháng 6, 2026, 12:25

      Được ông nhé, chỉ cần long long cho bài này


  • 0
    thanngocmai  đã bình luận lúc 21, Tháng 2, 2025, 15:50

    e thắc mắc chút: tại sao test 1 lại ra 45 mà ko phải 18 = 15+3 ??


    • 0
      luuthanhdatbienhoak66  đã bình luận lúc 24, Tháng 8, 2025, 11:36

      vi mỗi lần mua bao nhiêu phải đặt hết nhưng mà mỗi chồng chỉ để được 1 lần


  • -9
    Groot  đã bình luận lúc 2, Tháng 9, 2024, 15:53

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


  • -22
    vuongbankien012  đã bình luận lúc 2, Tháng 9, 2024, 5:24

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