Giải bài toán những chiếc gậy trong Java

Những chiếc gậy

Bài toán:

George có những chiếc gậy với chiều dài như nhau và chặt chúng thành những đoạn có chiều dài ngẫu nhiên cho đến khi tất cả các phần trở thành đều có chiều dài tối đa là 50 đơn vị. Bây giờ anh ta muốn ghép các đoạn lại như ban đầu nhưng lại quên mất nó như thế nào và chiều dài ban đầu của chúng là bao nhiêu. Hãy giúp George thiết kế chương trình để ước tính nhỏ nhất có thể của chiều dài những cái gậy này. Tất cả chiều dài được biểu diễn bằng đơn vị là những số nguyên lớn hơn 0.

Input. Dữ liệu vào trong file Input.txt chứa các khối mỗi khối 2 dòng. Dòng đầu tiên chứa số phần của chiếc gậy sau khi cắt. Dòng thứ 2 là chiều dài của các phần này cách nhau bởi một dấu cách. Dòng cuối cùng kết thúc file Input là số 0.

Output. Kết quả ra trong file Output.txt chứa chiều dài nhỏ nhất có thể của những cái gậy, mỗi chiếc trong mỗi khối trên một dòng.

Để giải bài toán trên trong Java, chúng ta có thể sử dụng thuật toán tìm kiếm nhị phân (binary search) để tìm kiếm độ dài tối thiểu của chiếc gậy.

Bước 1: Đọc dữ liệu vào từ file Input.txt.

Bước 2: Tìm độ dài nhỏ nhất của chiếc gậy bằng cách sử dụng thuật toán tìm kiếm nhị phân. Đặt l = 1, r = 10^9 (giả sử độ dài lớn nhất của chiếc gậy là 10^9) và thực hiện vòng lặp sau:

  • Đặt mid = (l + r) / 2.
  • Tính tổng độ dài của các phần gậy khi cắt thành các đoạn có độ dài tối đa là mid.
  • Nếu tổng độ dài nhỏ hơn hoặc bằng số phần của chiếc gậy, đặt r = mid – 1.
  • Ngược lại, đặt l = mid + 1.

Kết thúc vòng lặp, giá trị l chính là độ dài nhỏ nhất của chiếc gậy.

Bước 3: Ghi kết quả ra file Output.txt.

Dưới đây là đoạn code minh họa:

import java.util.*;
import java.io.*;

public class Main {
    public static void main(String[] args) throws Exception {
        Scanner input = new Scanner(new File("Input.txt"));
        PrintWriter output = new PrintWriter(new File("Output.txt"));

        while (true) {
            int n = input.nextInt();
            if (n == 0) break;
            int[] a = new int[n];
            for (int i = 0; i < n; i++) {
                a[i] = input.nextInt();
            }
            int l = 1, r = (int) 1e9;
            while (l <= r) {
                int mid = (l + r) / 2;
                int sum = 0;
                for (int i = 0; i < n; i++) {
                    sum += (a[i] + mid - 1) / mid; // làm tròn lên đến đoạn nguyên mới tính tổng
                }
                if (sum <= n) r = mid - 1;
                else l = mid + 1;
            }
            output.println(l);
        }

        input.close();
        output.close();
    }
}

Trả lời

Email của bạn sẽ không được hiển thị công khai. Các trường bắt buộc được đánh dấu *