Olympic 30/4 2016 - Khối 11 - Bài 1 - Robot táo

Xem dạng PDF
Gửi bài giải
Điểm: 1,70 (OI)
Giới hạn thời gian: 2.0s
Giới hạn bộ nhớ: 256M
Input: APROBOT.INP
Output: APROBOT.OUT
Nguồn bài:
Olympic 30/4
Dạng bài
Ngôn ngữ cho phép
C, C++, Go, Java, Kotlin, Pascal, PyPy, Python, Rust, Scratch

Một nhà máy chế biến hoa quả đang chế biến một sản phẩm từ táo. Nhà máy này đã có một dây chuyền sản xuất gồm nhiều công đoạn. Trong đó công đoạn đầu tiên, có ~N~ quả táo với trọng lượng đã biết được đưa ngẫu nhiên lên băng chuyền thành hàng dọc và được đánh số từ ~1~ đến ~N~. Chúng được ngầm phân thành ~M = [N/K]~ đoạn, mỗi đoạn gồm đúng ~K~ quả (~N~ là bội của ~K~). Các đoạn này cũng được đánh số từ ~1~ đến ~M~, kể từ đầu băng chuyền. Do yêu cầu kỹ thuật, chúng cần được sắp xếp lại sao cho:

  • Đoạn ~1~ sẽ gồm ~K~ quả có trọng lượng lớn nhất trong số các quả có mặt trên băng chuyền.

  • Nếu ~M > 1~ thì đoạn thứ ~i (i = 2, ..., M)~ sẽ ~K~ quả táo lớn nhất trong số các quả còn lại (không có mặt trong các đoạn từ ~1~ đến ~i-1~).

Một robot sẽ di chuyển dọc theo băng chuyền để thực hiên yêu cầu kỹ thuật nói trên. Mỗi thao tác của robot sẽ gồm việc rút ra khỏi băng chuyền ~1~ quả táo (các quả còn lại được dồn lại) rồi chèn quả táo này vào vị trí thích hợp trên băng chuyền (bao gồm cả vị trí đầu và cuối dãy).

Yêu cầu: Hãy viết chương trình tính xem cần thực hiện ít nhất bao nhiêu thao tác để xếp lại số táo trên băng chuyền theo đúng yêu cầu kỹ thuật.

Input

Vào từ tệp văn bản APROBOT.INP gồm:

  • Dòng đầu gồm hai số nguyên ~N~ và ~K~ ~(1 \le K \le N \le 5000);~

  • Dòng thứ hai ghi N số nguyên ~W_i~ ~(1 \le W_i \le 1000, i = 1, 2, ..., N)~ là số đơn vị trọng lượng của quả táo ~i~.

Các số trên cũng mỗi hàng đều được ghi cách nhau bởi ít nhất một dấu cách.

Output

Ghi ra tệp văn bản APROBOT.OUT duy nhất một số nguyên, là số thao tác ít nhất robot cần thực hiện.

Scoring

~50\%~ số test ứng với ~50\%~ số điểm của bài có ~(N \le 100)~.

Sample Input 1

6 2
7 3 2 5 9 1

Sample Output 1

2

Sample Input 2

6 2
7 8 9 5 3 5

Sample Output 2

1

Bình luận

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


  • 1
    TranThienPhuc2657  đã bình luận lúc 9, Tháng 7, 2026, 16:47 ← sửa 2

    Comment này spoil thuật

    Mình sẽ không đi vào chi tiết cách làm mà chỉ đề cập ý tưởng

    Đây sẽ là một hướng khác của subtask 2 so với editorial của bài này

    Khi làm subtask 1 bằng thuật ~\displaystyle \mathcal O \left(\frac{n^3} k\right)~, ta lưu cái vị trí mà làm tối ưu cho ~\mathrm{dp}[i][j]~ hiện tại là ~\mathrm{opt}[i][j]~.

    Khi in mảng ~\mathrm{opt}[i][j]~ này ra thì ta thấy là với mỗi hàng ~i~ thì các ~\mathrm{opt}[i][j]~ cũng tăng khi ~j~ tăng. Nên ta có thể sử dụng DP DNC để tối ưu xuống thành ~\displaystyle \mathcal O \left( \frac {n^2} k \log n \right)~

    Thực tế, code của mình chạy trong ~0.31 \rm s~, tương đối nhanh. Mình nộp lại thì nó lên ~0.7 \rm s~

    Dự đoán, suy nghĩ của mình về thời gian chạy này

    Có thể do ~k~ ngẫu nhiên nên là nó ít khi đạt tới mức ~\mathcal O(n^2 \log n)~.

    Giả sử nếu lấy trung bình là ~k~ rơi vào ~\displaystyle \frac n 2~ thì độ phức tạp trung bình thường có xu hướng rơi vào khoảng ~\mathcal O(n \log n)~


  • 3
    TranThienPhuc2657  đã bình luận lúc 9, Tháng 7, 2026, 13:57 ← chỉnh sửa

    Comment này giải thích cho các bạn theo hướng tiếp cận tham lam mà không hiểu tại sao mình lại sai.

    Cách làm tham lam mình đề cập ở đây là cách làm có số test đúng là ~31/52~ mà nhiều bạn đạt được.

    Giải thích thuật tham lam

    Ý tưởng:

    Sẽ có hai tập: một tập là sẽ được chọn và di chuyển, còn một cái thì để yên. Thay vì đếm số cái được chọn để thay đổi ít nhất thì ta sẽ đếm số cái được để yên nhiều nhất, đáp án là ~n~ trừ đi phần đó.

    Nhận xét

    Giả sử ban đầu ta biết được cái đoạn nó sẽ tới, khi này thì xét một số vị trí được chọn là sẽ đứng im thì một cách chọn hợp lệ là cách chọn mà cái phần tử ban đầu được ở sau nó sẽ tới được cái đoạn mà lớn hơn hoặc bằng cái phần tử ban đầu được ở trước.

    Ví dụ: ~9~ ở đoạn ~1~ và ~5~ ở đoạn ~2~, ban đầu ~9~ đứng trước ~5~ thì nếu giữ hai cái đứng im thì vẫn được do là ~9~ ở đoạn trước ~5~ (~1 < 2~), nhưng nếu mà ~5~ ban đầu được đứng trước ~9~ thì ~5~ ở đoạn ~2~ nên buộc phải di chuyển đi để nó ra sau ~9~ (~2 > 1 \implies~ không thỏa, cần để ~5~ sau ~9~ cho ~1 < 2~ mới thỏa).

    Cách làm

    Sort lại mảng xong rồi đánh số thứ tự của đoạn mà phần tử hiện tại sẽ ở, nếu mà nhiều cái thì ưu tiên cái nào mà ban đầu vị trí nó nhỏ hơn thì sẽ cho vào nhóm nhỏ hơn.

    Với định nghĩa cách chọn đoạn cố định như vậy (số ở sau thì đoạn cũng phải sau hoặc cùng) thì tức là tìm độ dài dãy con không giảm dài nhất.

    Độ phức tạp:

    ~\mathcal O(n \log n)~ hoặc ~\mathcal O(n^2)~ tùy vào cách tính bài toán dãy con không giảm dài nhất.

    Ví dụ cách hoạt động

    Lấy test đề bài: 

    6 2
7 3 2 5 9 1

    Dễ dàng thấy được: ~9; 7~ thuộc nhóm ~1~, ~5; 3~ thuộc nhóm ~2~ và ~2; 1~ thuộc nhóm ~3~

    Ánh xạ mảng theo cái thứ tự nhóm của từng phần tử: 

    1 2 3 2 1 3

    Dãy con không giảm dài nhất có độ dài là: ~4 \, (1; 2; 2; 3)~

    Như vậy số thao tác ít nhất là: ~6 - 4 = \boxed{2}~

    Lí do cách này sai

    Trường hợp có nhiều phần tử bằng nhau thì chúng có thể được thay thế cho nhau, việc gán nhóm trước, có cái lớn hơn, có cái nhỏ hơn làm mất đi tính linh hoạt của chúng.

    Không phải là cứ ban đầu ở sau là lúc cuối cũng sẽ ở sau, có khi sẽ lên trước được nên việc gắn nhóm như là việc ngăn chặn cho nó lên trước.

    Ví dụ phản chứng

    6 2
3 3 4 7 3 4

    Đáp án theo cách tham lam

    Theo quy tắc thì sẽ đánh số nhóm như sau:

    • ~7; 4~: nhóm ~1~

    • ~4; 3~: nhóm ~2~

    • ~3; 3~: nhóm ~3~

    Nếu mà cùng giá trị thì sẽ ưu tiên vị trí ban đầu bé hơn thì sẽ ở nhóm bé hơn.

    Có được mảng sau ánh xạ bằng vị trí nhóm của từng phần tử:

    2 3 1 1 3 2

    Dãy con không giảm dài nhất có độ dài là ~3 \, (\{ 1; 1; 3 \} / \dots)~

    Số thao tác ít nhất là: ~6 - 3 = \boxed{3}~

    Phản chứng

    Thay đổi cách gắn nhóm sau và vẫn thỏa việc đánh số nhóm (không tuân theo thuật toán tham lam ban đầu):

    3 3 1 1 2 2

    Số ~3~ ở vị trí ~5~ ban đầu cũng là số ~3~ nên cũng có thể ở nhóm ~2~ được.

    Khi này dãy tăng không giảm dài nhất có độ dài là ~4 \, (1; 1; 2; 2)~

    Số thao tác ít nhất là: ~6 - 4 = \boxed{2}~


  • 2
    Thien2009  đã bình luận lúc 28, Tháng 3, 2025, 22:56

    dung tham lam khong on lam


  • 0
    nquynh2422  đã bình luận lúc 23, Tháng 3, 2025, 7:52 ← chỉnh sửa

    test 2 ra 0