Diện tích nhỏ nhất lớn nhất sau K lần cắt hình chữ nhật trong C++

Cho hình chữ nhật cạnh n, m. Cắt đúng K lần (song song cạnh). Tìm giá trị lớn nhất của diện tích nhỏ nhất trong các mảnh sau khi cắt.

Thuật toán

• Nếu K > n+m-2 → không thể.
• Nếu K < max(n,m)-1: cắt tất cả K lần trên cạnh dài hơn → max( m*(n/(K+1)), n*(m/(K+1)) ).
• Ngược lại: cắt hết cạnh ngắn, phần còn lại cắt cạnh dài → max( m/(K-n+2), n/(K-m+2) ).

Ví dụ triển khai (C++)

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

void max_area(int n, int m, int k) {
    if (k > n + m - 2) { cout << "Not possible" << endl; return; }
    int result;
    if (k < max(m,n) - 1)
        result = max(m * (n / (k+1)), n * (m / (k+1)));
    else
        result = max(m / (k - n + 2), n / (k - m + 2));
    cout << result << endl;
}

int main() {
    int n = 3, m = 4, k = 1;
    max_area(n, m, k);
    return 0;
}

Đầu ra

6