Hình chữ nhật rỗng lớn nhất có cơ sở nằm trên trục x

Question

Original Problem: Problem 2

Trong không gian hình chữ nhật có chiều cao 500 và chiều rộng là 10^5, chúng tôi được cung cấp N điểm.

Chúng ta phải tìm ra hình chữ nhật phụ lớn nhất có cơ sở nằm trên trục x và không chứa bất kỳ điểm nào trong nội thất thích hợp của nó (nhưng có thể chứa chúng ở các cạnh của nó).

tôi đã cố gắng một O (chiều rộng^2) Thuật toán:

#include <iostream> 
#include <algorithm> 

const int nWidth = 100000; 
const int nHeight = 500; 

int main(){ 

    int *nMaxHeights = new int[nWidth]; 
    std::fill (nMaxHeights, nMaxHeights+nWidth, nHeight); 

    int N; 
    std::cin >> N; 
    for (int x,y,iii=0; iii < N; iii++){ 
    std::cin >> x >> y; 
    nMaxHeights[x] = std::min(y+1, nMaxHeights[x]); 
    } 

    int maxArea = 0; 
    for (int jjj,iii=0; iii < nWidth; iii++){ 
    for (jjj=iii; jjj < nWidth; jjj++){ 
     if (nMaxHeights[jjj] < nMaxHeights[iii]) 
     break; 
    } 
    maxArea = std::max((jjj-iii+1)*nMaxHeights[iii],maxArea); 
    } 

    std::cout << maxArea; 

    return 0; 
} 

Nó hoạt động, nhưng rõ ràng là nhận (Giới hạn Execution Time Exceeded) TLE.

Làm cách nào để tôi làm tốt hơn?

Answer 1

Sự cố thú vị. Cảm ơn bạn đã chỉ ra những điều này.

Tôi đã sử dụng thuật toán có quy mô O(N) cho số lớn hơn N (số điểm) và phân phối điểm ngẫu nhiên. Ý tưởng đằng sau nó: Mỗi hình chữ nhật sẽ bị ràng buộc bởi một số điểm.

1. Nếu có nhiều điểm hơn cho một giá trị x, chỉ có giá trị một giá trị y thấp nhất được sử dụng.
2. Đầu tiên kiểm tra các điểm cực đại x; hầu hết các bên phải và bên trái nhất, mở rộng một hình chữ nhật để resp. giới hạn.
3. Sau đó đi đến điểm tận cùng bên phải và cố gắng tạo hình chữ nhật bao gồm cả hình chữ nhật. Có hai khả năng:
   1. điểm này nằm trên cạnh ngang: Tìm hai hàng xóm, trái và phải, có giá trị y thấp hơn và sử dụng chúng làm điểm trên cạnh trái. Cạnh phải. Nếu không có hàng xóm bên trái/bên phải, hãy sử dụng phần cuối của không gian.
   2. điểm này nằm trên cạnh thẳng đứng: Tìm điểm bên trái bên trái, sử dụng giới hạn (y) của không gian làm cạnh ngang.
4. Đối với mỗi điểm, tính toán các khu vực hình chữ nhật có thể có (hai khả năng ở trên) và nếu có lớn hơn khu vực lớn nhất hiện tại, hãy cập nhật khu vực lớn nhất.

Dưới đây là một số thực hiện mẫu trong python, http://pastebin.com/068ByYwh, nhưng tôi không tích cực, rằng nó không chứa lỗi ;-)

Answer 2

Hãy tưởng tượng chỉ là một điểm. Có ba hình chữ nhật có thể có: bên dưới điểm, bên trái của nó và bên phải của nó.

Giả sử hiện có hai điểm. Hãy nhìn vào cái gần hơn ở phía dưới đầu tiên. Một lần nữa, có ba trường hợp ở bước này. Có một hình chữ nhật bên dưới điểm này. Ngoài ra còn có một hình chữ nhật ở phía đối diện của điểm khác. Và có mặt với điểm khác, nơi có nhiều hình chữ nhật hơn. IOW, nếu bạn nhìn vào các điểm dưới cùng, thì mỗi điểm có một hình chữ nhật bên dưới và điểm này chia không gian thành hai dải dọc, trong đó có các điểm khác, tương tự như hình chữ nhật bên dưới và chia nhỏ không gian.Vì vậy, có vẻ hợp lý khi sắp xếp các điểm theo cả Y và X (có lẽ, bằng cách đặt chúng thành hai nút được sắp xếp theo thứ tự, một được sắp xếp theo Y (vì vậy bạn có thể di chuyển trong Y) và cái kia được sắp xếp theo X (để bạn có thể di chuyển/tìm kiếm trái/phải)), đó là N * log (N), và sau đó đệ quy truy cập tất cả các điểm dưới cùng, phân chia không gian thích hợp, trông giống như một N * log (N) khác.