Cắt Dây (CATDAY)

Nguồn: Bài tập được hỏi trong nhóm lập trình Độ khó: Trung bình Tìm kiếm nhị phân Vét cạn Tư duy

Đề bài

CẮT DÂY (CATDAY)

Để chuẩn bị cho ngày lễ Noel bạn An chuẩn bị $N$ đoạn dây trang trí (đoạn dây thứ $i$ có độ dài $a_i$) và $M$ đèn. An muốn cắt $N$ đoạn dây này thành $M$ đoạn bằng nhau để treo đèn, mỗi dây treo 1 đèn. Yêu cầu mỗi đoạn có độ dài nguyên. Không nhất thiết cắt hết tất cả đoạn dây ban đầu và phần thừa cắt đi có thể có độ dài khác 0.

Yêu cầu: Hãy giúp An tìm độ dài lớn nhất mà đoạn dây có thể nhận được. Nếu không thể cắt thì đưa ra số 0.

Dữ liệu vào: Tệp văn bản catday.inp:

• Dòng đầu chứa 2 số nguyên $N$, $M$.
• Dòng thứ $i$ trong $N$ dòng sau chứa số nguyên $a_i$.

Kết quả ra: Tệp văn bản catday.out ghi kết quả trên 1 dòng dưới dạng số nguyên.

(Code trong bài đọc/ghi chuẩn – bàn phím/màn hình. Nếu nộp ở nơi bắt dùng file thì các bạn thêm freopen("catday.inp", "r", stdin); freopen("catday.out", "w", stdout); vào đầu hàm main nhé.)

catday.inp

4 11
802
743
547
539

catday.out

200

Lời mở đầu

Bữa giờ LeetCode hoài sợ anh em ngán 😅 Nay mình đi comment dạo thấy bài này cũng được nên đăng để anh em thử sức nhé. Bài này là của một bạn đăng trong nhóm lập trình hỏi ý tưởng tối ưu, bạn ấy "nghĩ cả chiều không ra mà deadline sắp dí tới" 🤣. Thật ra đây là một bài kinh điển của dạng tìm kiếm nhị phân theo kết quả, nắm được dạng này rồi thì gặp lại là xử lý trong vài phút thôi. Chúc anh em học tốt và gặt hái nhiều thành công 😇.

Bạn nào muốn thử nộp bài để hệ thống chấm xem có đúng hay không thì link bài đây nhé:

Link nộp bài

Bấm vào nút bên dưới để nộp bài và được hệ thống CLUE OJ chấm tự động.

Nộp bài trên CLUE OJ

Giải thích ví dụ cho bạn nào chưa hiểu đề: có 4 sợi dây dài $802, 743, 547, 539$ và cần $M = 11$ đoạn bằng nhau. Nếu chọn độ dài mỗi đoạn là 200:

Sợi dây	802	743	547	539	Tổng
Cắt đoạn 200	4 (thừa 2)	3 (thừa 143)	2 (thừa 147)	2 (thừa 139)	11 ≥ 11 ✔
Cắt đoạn 201	3 (thừa 199)	3 (thừa 140)	2 (thừa 145)	2 (thừa 137)	10 < 11 ✘

Độ dài 200 cắt được đủ 11 đoạn (phần thừa bỏ đi, đề cho phép), còn 201 thì chỉ được 10 đoạn, không đủ. Mà độ dài càng lớn thì cắt được càng ít đoạn, nên mọi độ dài $\gt 200$ cũng không đủ ⇒ đáp án là 200. Lưu ý mỗi đoạn phải nằm trọn trong một sợi dây, không được nối 2 mẩu thừa lại với nhau nha.

Lộ trình lời giải, bấm vào từng phần để nhảy tới:

Cách 1Thử từng độ dài từ lớn xuống · O(N · max a)Cách 2Tìm kiếm nhị phân độ dài · O(N · log max a)

Cách 1Thử từng độ dài từ lớn xuống – O(N · max a)

Nếu đã chốt độ dài mỗi đoạn là $len$ thì việc đếm xem cắt được bao nhiêu đoạn rất dễ: sợi dây dài $a_i$ cắt được $\left\lfloor \dfrac{a_i}{len} \right\rfloor$ đoạn (chia nguyên), phần dư bỏ đi. Gọi

Hàm đếm

$f(len) = \displaystyle\sum_{i=1}^{N} \left\lfloor \dfrac{a_i}{len} \right\rfloor$ = số đoạn dài $len$ cắt được. Độ dài $len$ hợp lệ khi $f(len) \ge M$.

Độ dài một đoạn không thể vượt quá sợi dây dài nhất $mx = \max a_i$ (vì đoạn phải nằm trọn trong một sợi). Vậy cách đơn giản nhất là thử $len = mx, mx - 1, \ldots, 1$: gặp độ dài đầu tiên có $f(len) \ge M$ thì đó là độ dài lớn nhất, in ra và dừng. Nếu thử hết tới 1 mà vẫn không đủ (tức là tổng độ dài cả $N$ sợi còn chưa tới $M$) thì in $0$.

Source code để các bạn tham khảo nếu làm theo hướng này:

#include <bits/stdc++.h>
using namespace std;

int main(){
    long long n, m;
    cin >> n >> m;
    vector<long long> a(n);
    long long mx = 0;
    for(int i = 0; i < n; i++){
        cin >> a[i];
        mx = max(mx, a[i]);
    }
    for(long long len = mx; len >= 1; len--){
        long long cnt = 0;
        for(int i = 0; i < n; i++){
            cnt += a[i] / len;
        }
        if(cnt >= m){
            cout << len;
            return 0;
        }
    }
    cout << 0;
    return 0;
}

import sys

data = sys.stdin.read().split()
n, m = int(data[0]), int(data[1])
a = [int(x) for x in data[2:2 + n]]
mx = max(a) if a else 0
ans = 0
for length in range(mx, 0, -1):
    cnt = 0
    for x in a:
        cnt += x // length
    if cnt >= m:
        ans = length
        break
print(ans)

Đánh giá độ phức tạp của cách làm này:

• Không gian: lưu mảng $a$ ⇒ $O(N)$.
• Thời gian: trường hợp xấu nhất phải thử gần hết $mx$ độ dài, mỗi lần đếm mất $O(N)$ ⇒ $O(N \cdot mx)$.

Không gian$O(N)$

Thời gian$O(N \cdot \max a_i)$

Đây chính là chỗ bị TLE

Với độ dài dây cỡ vài trăm như ví dụ thì cách này chạy vèo vèo. Nhưng nếu $a_i$ lên tới $10^9$ và $N$ cỡ $10^5$ thì phải làm tới $10^{14}$ phép tính – mình thử với $N = 10^5$, $a_i \le 10^9$, $M = 10^9$ thì sau 10 giây chương trình vẫn chưa ra kết quả. Đề không ghi giới hạn nhưng bạn hỏi bài đang cần "ý tưởng tối ưu", nên chắc chắn test lớn sẽ không cho qua kiểu này.

Cách 2Tìm kiếm nhị phân độ dài – O(N · log max a)

Nhìn lại hàm $f(len)$: độ dài mỗi đoạn càng lớn thì số đoạn cắt được càng ít (mỗi $\left\lfloor a_i / len \right\rfloor$ chỉ có thể giảm hoặc giữ nguyên khi $len$ tăng). Nên nếu xếp các độ dài $1, 2, \ldots, mx$ thành một hàng thì nó chia làm đúng 2 khúc:

Nhận xét then chốt – tính đơn điệu

1✔2✔…200✔201✘…802✘

(ví dụ đề: xanh = $f(len) \ge M$, đỏ = $f(len) \lt M$)

Một khúc đầu toàn độ dài cắt đủ, rồi từ một chỗ nào đó trở đi toàn độ dài không đủ. Đáp án là ô ✔ cuối cùng. Tìm "ranh giới" trong một dãy đơn điệu như vậy thì dùng tìm kiếm nhị phân.

Cụ thể, giữ đoạn $[l, r]$ chứa đáp án, ban đầu $l = 1$, $r = mx$, $ans = 0$. Mỗi bước lấy $mid = (l + r) / 2$ và đếm $f(mid)$:

• Nếu $f(mid) \ge M$: độ dài $mid$ cắt được ⇒ ghi nhận $ans = mid$, nhưng biết đâu còn dài hơn nữa vẫn được ⇒ tìm tiếp bên phải: $l = mid + 1$.
• Ngược lại: $mid$ quá dài ⇒ mọi độ dài $\ge mid$ đều không được ⇒ tìm bên trái: $r = mid - 1$.

Khi $l \gt r$ thì $ans$ chính là độ dài lớn nhất cắt đủ $M$ đoạn. Nếu chưa lần nào cắt đủ thì $ans$ vẫn là $0$ – đúng yêu cầu "không thể cắt thì đưa ra số 0" luôn, khỏi xử lý riêng 😎.

Mẹo nhớ dạng bài

Đề hỏi "giá trị lớn nhất / nhỏ nhất sao cho thỏa điều kiện", mà khi đã biết giá trị thì kiểm tra điều kiện rất dễ, và điều kiện có tính đơn điệu ⇒ nghĩ ngay tới tìm kiếm nhị phân theo kết quả. Các bài cắt gỗ, chia kẹo, xếp bò vào chuồng, máy sản xuất sản phẩm... đều là họ hàng của bài này.

Minh hoạ tìm kiếm nhị phân

Em nhập $M$ và độ dài các sợi dây rồi bấm Tiếp. Mỗi sợi dây được vẽ thành một thanh: phần xanh (hoặc đỏ nếu không đủ) là các đoạn dài $mid$ cắt được, phần xám là phần thừa bỏ đi. Thanh ngang phía trên cho biết đoạn $[l, r]$ đang tìm.

M Độ dài các sợi a_i

Ví dụ nhanh:

Source code để các bạn tham khảo nếu làm theo hướng này:

#include <bits/stdc++.h>
using namespace std;

long long n, m;
vector<long long> a;

long long dem(long long len){
    long long cnt = 0;
    for(int i = 0; i < n; i++){
        cnt += a[i] / len;
    }
    return cnt;
}

int main(){
    cin >> n >> m;
    a.resize(n);
    long long mx = 0;
    for(int i = 0; i < n; i++){
        cin >> a[i];
        mx = max(mx, a[i]);
    }
    long long l = 1, r = mx, ans = 0;
    while(l <= r){
        long long mid = (l + r) / 2;
        if(dem(mid) >= m){
            ans = mid;
            l = mid + 1;
        }
        else{
            r = mid - 1;
        }
    }
    cout << ans;
    return 0;
}

import sys


def dem(a, length):
    cnt = 0
    for x in a:
        cnt += x // length
    return cnt


def main():
    data = sys.stdin.buffer.read().split()
    n, m = int(data[0]), int(data[1])
    a = [int(x) for x in data[2:2 + n]]
    l, r, ans = 1, max(a) if a else 0, 0
    while l <= r:
        mid = (l + r) // 2
        if dem(a, mid) >= m:
            ans = mid
            l = mid + 1
        else:
            r = mid - 1
    print(ans)


main()

C++▶ Chạy tay từng dòng codeCách 2: tìm kiếm nhị phân độ dài len trong [1, max a], hàm dem(len) đếm số đoạn cắt được.

Dữ liệu vào (stdin) – sửa thoải mái4 11 802 743 547 539

Dữ liệu mẫu:

1#include <bits/stdc++.h>

2using namespace std;

3

4long long n, m;

5vector<long long> a;

6

7long long dem(long long len){

8 long long cnt = 0;

9 for(int i = 0; i < n; i++){

10 cnt += a[i] / len;

11 }

12 return cnt;

13}

14

15int main(){

16 cin >> n >> m;

17 a.resize(n);

18 long long mx = 0;

19 for(int i = 0; i < n; i++){

20 cin >> a[i];

21 mx = max(mx, a[i]);

22 }

23 long long l = 1, r = mx, ans = 0;

24 while(l <= r){

25 long long mid = (l + r) / 2;

26 if(dem(mid) >= m){

27 ans = mid;

28 l = mid + 1;

29 }

30 else{

31 r = mid - 1;

32 }

33 }

34 cout << ans;

35 return 0;

36}

ChậmVừaNhanhRất nhanh

Đánh giá độ phức tạp của cách làm này:

• Không gian: lưu mảng $a$ ⇒ $O(N)$.
• Thời gian: đoạn tìm $[1, mx]$ mỗi bước giảm một nửa nên chỉ có khoảng $\log_2 mx$ bước (với $mx = 10^9$ là cỡ 30 bước), mỗi bước gọi dem mất $O(N)$ ⇒ $O(N \log mx)$. Với $N = 10^5$ chỉ khoảng $3 \cdot 10^6$ phép chia, chạy tức thì nha các bạn.

Không gian$O(N)$

Thời gian$O(N \log \max a_i)$

Nhớ dùng long long cho biến đếm

Tổng số đoạn $\sum a_i / len$ có thể rất lớn: ví dụ $N = 10^5$ sợi dài $10^9$ với $len = 1$ là $10^{14}$ đoạn, vượt xa int. Vì vậy cnt, m, l, r, mid mình để hết long long cho chắc. Ngoài ra đừng bắt đầu tìm từ $l = 0$ – vì dem(0) sẽ chia cho 0 đó nha.

Ghi chú của mình: ảnh đề bạn ấy gửi không ghi giới hạn của $N$, $M$, $a_i$ nên mình phân tích theo giới hạn thường gặp ($N \le 10^5$, $a_i \le 10^9$). Code C++ và Python của cả 2 cách đã được kiểm tra với 400 bộ test ngẫu nhiên nhỏ, so với code vét cạn thử mọi độ dài – khớp hết (có cả trường hợp không cắt được, in 0). Với $N = 10^5$, $a_i \le 10^9$: cách 2 bản C++ chạy khoảng 0.16 giây, bản Python khoảng 0.3 giây; còn cách 1 chạy quá 10 giây vẫn chưa xong, đúng như phân tích.

Rất vui khi anh em nào đã đọc đến những dòng cuối cùng này. Anh em đọc chắc cũng mỏi mắt luôn chứ 😅 vậy anh em nghĩ người viết ra hết đống ở trên còn thế nào nữa 🤪. Vậy nên đừng tiếc gì cho mình một lời bình luận hoặc chia sẻ bài viết để động viên mình nè. Chúc anh em học tốt và gặt hái nhiều thành công 😇