PVHOI 2.0 - Bài 1: Chất lượng cuộc sống

Tác giả:

Dạng bài

Ngôn ngữ cho phép

C, C#, C++, Clang, Clang++, Cobol, D, ~~Groovy~~, Haskell, Java, JS, Kotlin, Lua, Node JS, ObjectiveC, OCaml, Output, Pascal, PHP, Prolog, Pypy, Pypy 3, Ruby, Rust, Scala, ~~Swift~~

Điểm: 2300 (p) Thời gian: 2.0s Bộ nhớ: 1G Input: bàn phím Output: màn hình

Thành phố Nồi Hạ có phân bổ dân cư hết sức đặc biệt: Thành phố có \(r \cdot c\) khu dân cư đựoc xếp dưới dạng lưới hình chữ nhật gồm \(r\) hàng và \(c\) cột. Các hàng được đánh số từ \(1\) đến \(r\), các cột được đánh số từ \(1\) đến \(c\). Khu dân cư nằm trên giao của hàng \(i\) và cột \(j\) được kí hiệu là \((i, j)\).

Trong đợt khảo sát vừa qua, lãnh đạo thành phố đã đi từng ngõ, gõ từng nhà để thu thập thông tin về chất lượng cuộc sống ở các khu dân cư. Tiếp đó, họ xếp hạng các khu dân cư bằng các con số phân biệt từ \(1\) đến \(r \cdot c\). Khu dân cư xếp hạng \(1\) có chất lượng cuộc sống tốt nhất. Khu dân cư xếp hạng \(r \cdot c\) có chất lượng tệ nhất. Khu dân cư được xếp hạng càng nhỏ thì chất lượng sống càng cao. Theo kết quả, khu dân cư \((i, j)\) được xếp hạng \(p_{i, j}\).

Từ kết quả xếp hạng, thành phố sẽ chọn ra một khu vực để tăng cường đầu tư nhằm nâng cao chất lượng cuộc sống ở đây. Thành phố quyết định rằng các khu dân cư được nâng cấp sẽ nằm trong một hình chữ nhật con có kích thước \(h \cdot w\) (gồm \(h\) hàng và \(w\) cột), với \(h\) và \(w\) là các số lẻ. Lãnh đạo thành phố muốn chọn những nơi chất lượng sống còn thấp để ưu tiên cải tạo, nhưng họ cần đưa ra một tiêu chí đánh giá chung cho một vùng hình chữ nhật kích thước \(h \cdot w\). Theo đó, "mức sống tiêu biểu" của một khu vực là trung vị của thứ hạng chất lượng cuộc sống của các khu dân cư bên trong đó. (xem phần dưới để biết định nghĩa về trung vị)

Khu vực được chọn để đầu tư phải có "mức sống tiêu biểu" lớn nhất (vì thứ hạng càng lớn thì chất lượng cuộc sống càng thấp) trong các khu vực có thể chọn. Bạn hãy giúp họ tìm ra "mức sống tiêu biểu" lớn nhất này nhé.

Giá trị trung vị của một dãy số \((a_1, a_2, \ldots, a_n)\) (với \(n\) là số lẻ) là giá trị thứ \(\frac{n+1}{2}\) (ở vị trí chính giữa) của dãy số sau khi dãy đã được sắp xếp theo thứ tự tăng dần. Ví dụ, trung vị của dãy \((22, 7, 97)\) là \(22\) (do dãy sau khi sắp xếp trở thành \((7, 22, 97)\); trung vị của dãy \((2, 2, 7, 1, 9, 9, 7)\) là \(7\) (do dãy sau khi sắp xếp trở thành \((1, 2, 2, 7, 7, 9, 9)\).

Input

Dòng đầu tiên chứa bốn số nguyên \(r\), \(c\), \(h\), \(w\) \((1 \leq h \leq r \leq 3000, 1 \leq w \leq c \leq 3000)\), lần lượt là kích thước của thành phố Nồi Hạ và kích thước vùng được chọn để nâng cao chất lượng cuộc sống. Dữ liệu vào đảm bảo \(h\) và \(w\) là các số lẻ.
Trong \(r\) dòng còn lại, dòng thứ \(i\) chứa \(c\) số nguyên \(p_{i, 1}, p_{i, 2}, \ldots, p_{i, c}\) \((1 \leq p_{i, j} \leq r \cdot c)\), trong đó \(p_{i, j}\) là thứ hạng chất lượng cuộc sống của khu \((i, j)\). Dữ liệu vào đảm bảo \(r \cdot c\) số này là đôi một phân biệt.

Output

In ra một số nguyên duy nhất là "mức sống tiêu biểu" lớn nhất của một khu vực có dạng hình chữ nhật kích thước \(h \cdot w\).

Scoring

Bộ test của bài được chia làm các subtask như sau:

Subtask \(1\) (\(9.1\) điểm): \(h = w = 1\)
Subtask \(2\) (\(9.1\) điểm): \(h = r\) và \(w = c\)
Subtask \(3\) (\(14.7\) điểm): \(r, c \leq 30\)
Subtask \(4\) (\(14.7\) điểm): \(r, c \leq 100\)
Subtask \(5\) (\(7\) điểm): \(r, c \leq 300\)
Subtask \(6\) (\(7\) điểm): \(r, c \leq 1000\)
Subtask \(7\) (\(8.4\) điểm): Không có ràng buộc gì thêm.

Điểm tối đa của bài là \(70\) điểm.

Example

Test 1

Input

5 5 3 3
5 11 12 16 25
17 18 2 7 10
4 23 20 3 1
24 21 19 14 9
6 22 8 13 15

Output

Note

Trong ví dụ ở trên, lãnh đạo thành phố nên chọn hình chữ nhật kích thước \(3 \cdot 3\) ở góc trái dưới làm khu vực được nâng cấp. Thứ hạng của các khu dân cư bên trong khu vực này lần lựot là \(4, 23, 20, 24, 21, 19, 6, 22, 8\) (được sắp xếp theo thứ tự tăng dần là \(4, 6, 8, 19, 20, 21, 22, 23, 24\)). Nhu vậy, ``mức sống tiêu biểu'' của khu vực này là \(20\).

Bình luận

include <iostream>

include <vector>

include <algorithm>

include <set>

using namespace std;

int getMedian(vector<int>& values) {
int n = values.size();
sort(values.begin(), values.end());
return values[n / 2]; // For odd n, this gives the middle element
}

int getMaxTypicalLivingLevel(int r, int c, int h, int w, const vector<vector\<int>>& rankings) {
int maxMedian = -1;

// Process each possible top-left corner for the h x w submatrix
for (int startRow = 0; startRow <= r - h; ++startRow) {
    for (int startCol = 0; startCol <= c - w; ++startCol) {
        vector<int> currentWindow;

        // Collect all values in the h x w window
        for (int i = 0; i < h; ++i) {
            for (int j = 0; j < w; ++j) {
                currentWindow.push_back(rankings[startRow + i][startCol + j]);
            }
        }

        // Get the median for this window
        int median = getMedian(currentWindow);
        maxMedian = max(maxMedian, median);
    }
}

return maxMedian;

}

int main() {
int r, c, h, w;
cin >> r >> c >> h >> w;
vector<vector\<int>> rankings(r, vector<int>(c));

for (int i = 0; i < r; ++i) {
    for (int j = 0; j < c; ++j) {
        cin >> rankings[i][j];
    }
}

int result = getMaxTypicalLivingLevel(r, c, h, w, rankings);
cout << result << endl;

return 0;

}

0

anhduc11092014 1:11 p.m. 5 Tháng 6, 2024

help

1 phản hồi