用c++从键盘输入一百个整数 从中找出最大值和最小值

好的，以下是使用C++语言从键盘输入一百个整数，并找出其中的最大值和最小值的代码：

#include <iostream>
using namespace std;

int main() {
    int numbers[100];
    for (int i = 0; i < 100; i++) {
        cout << "请输入第" << i+1 << "个整数：";
        cin >> numbers[i];
    }
    int max_num = numbers[0];
    int min_num = numbers[0];
    for (int i = 1; i < 100; i++) {
        if (numbers[i] > max_num) {
            max_num = numbers[i];
        }
        if (numbers[i] < min_num) {
            min_num = numbers[i];
        }
    }
    cout << "您输入的100个整数中，最大值为：" << max_num << endl;
    cout << "您输入的100个整数中，最小值为：" << min_num << endl;
    return 0;
}

请您在控制台或者集成开发环境中执行该代码，并按照提示输入100个整数，程序会找出您输入的100个整数中的最大值和最小值，并将其打印输出。

相关问题

c++求若干整数最大值最小值平均值最后输入的标记值为零（数值范围大于零小于一百）

好的,我来为您介绍如何使用C++来求若干整数的最大值、最小值和平均值,最后输入的标记值为零(数值范围大于零小于一百)。以下是一个示例代码:

#include <iostream>
using namespace std;

int main() {
    int num;
    int max, min, sum = 0;
    int count = 0;

    while (true) {
        cout << "请输入一个整数(0结束): ";
        cin >> num;

        if (num == 0) {
            break;
        }

        if (num < 1 || num > 99) {
            cout << "输入的数字, 请重新输入。" << endl;
            continue;
        }

        if (count == 0) {
            max = min = num;
        } else {
            if (num > max) {
                max = num;
            }
            if (num < min) {
                min = num;
            }
        }

        sum += num;
        count++;
    }

    if (count > 0) {
        cout << "最大值: " << max << endl;
        cout << "最小值: " << min << endl;
        cout << "平均值: " << (double)sum / count << endl;
    } else {
        cout << "没有输入有效的数字。" << endl;
    }

    return 0;
}

这个程序的工作原理如下:

1. 我们使用一个while循环来持续接收用户输入的整数。

2. 每次输入后,我们首先检查是否为0。如果是0,我们使用break语句退出循环。

3. 然后,我们检查输入的数字是否在1到99之间。如果不是,我们提示用户重新输入。

4. 对于有效的输入,我们更新最大值(max)和最小值(min)。如果这是第一个有效的输入,我们同时将max和min设置为这个数字。

5. 我们将输入的数字加到sum中,并增加计数器count。

6. 循环结束后,如果我们至少有一个有效的输入,我们计算并输出最大值、最小值和平均值。

7. 如果没有有效的输入,我们输出相应的提示信息。

这个程序满足了您的要求,包括输入范围限制(大于0,小于100),并使用0作为结束标记。

1. jxcakak 题目ID：9475拓展题100分 最新提交： Time Limit Exceeded 50 分 历史最高： Time Limit Exceeded 50 分 时间限制: 2000ms 空间限制: 524288kB 题目描述 时间：2s 空间：512M 题目描述 给定一个w*h的矩形，每个方格内有数，求一个n*n的正方形，使得正方形内部最小值加最大值的值最小。 你只需要输出这个数值 输入格式 第一行三个正整数w,h,n w,h <=2000,n <=min(w,h) 接下来w行每行h个数描述这个矩阵，保证矩阵中所有数非负并且不超过1e9 输出格式 一个整数. 样例输入 5 4 2 1 2 5 6 0 17 16 0 16 17 2 1 2 10 2 1 1 2 2 2 样例输出 3 约定 对于10%的数据，max(w,h)<=10 对于20%的数据，max(w,h)<=100 对于40%的数据，max(w,h)<=500 对于60%的数据，max(w,h)<=1000 对于100%的数据，max(w,h)<=2000 请给出C++TIJIE DAIMA

<think>嗯，这个问题看起来是要在给定的二维矩阵中找到所有n*n的正方形区域，然后计算每个区域的最小值和最大值之和，最后找出这些和中的最小值。不过数据规模很大，w和h可以达到2000，n也可能到2000。直接暴力枚举每个n*n区域然后找最大最小值显然会超时，时间复杂度是O(w*h*n²)，对于2000来说，n²是四百万，乘上w*h的话，总次数会是2000*2000*4e6=16e12次，这显然无法在2秒内完成。所以必须用更高效的方法。

首先，我得想到怎么快速计算每个n*n窗口的最大值和最小值。这时候应该想到滑动窗口的单调队列方法。之前在二维矩阵中处理滑动窗口的最值问题，通常是用两个一维的单调队列分别处理行和列的方向。例如，先对每一行处理，得到每个位置在行内长度为n的窗口的最值，然后再对这些结果按列处理，得到最终的二维窗口的最值。这种方法的时间复杂度是O(w*h)，应该可以处理2000x2000的数据。

那具体怎么做呢？比如说，对于每一行，先预处理每个位置在行方向上的窗口最大值和最小值。例如，对于每个元素matrix[i][j]，在行i上，从j到j+n-1的位置的最大值。这可以用单调队列来维护，每个窗口的移动时，队列保存可能成为最大值的元素的下标。类似地处理最小值。这一步处理之后，每个位置对应的行窗口的最大值和最小值会被记录下来。

然后，再对每一列处理，此时处理的是之前得到的行窗口结果。比如，对于最大值数组，在列方向上，对每个长度为n的窗口取最大值，这样就能得到整个n*n区域的最大值。同样处理最小值数组，得到整个区域的最小值。最后遍历所有可能的窗口，计算最大值加最小值的最小值即可。

那具体怎么实现呢？我需要为每个行处理两个数组，max_row和min_row。然后对于每列，处理这些数组得到最终的max和min的二维数组。

举个例子，假设原矩阵是5行4列，n=2。对于第一行来说，处理每个可能的窗口长度为2的列，得到每行的max_row和min_row。比如原第一行是1,2,5,6。那么max_row的第一行的窗口是max(1,2)=2，max(2,5)=5，max(5,6)=6。对应的列位置是0和1的位置。然后处理列方向，每个列中的窗口长度为n的行。比如对于max_row数组中的某一列，假设是j列，处理每个i行，得到i到i+n-1行的max，这样就能得到整个n*n窗口的max。

所以，整个过程需要两次滑动窗口处理：一次行方向，一次列方向。每次处理都需要分别处理最大值和最小值。

那代码的大体结构应该是这样的：

1. 输入矩阵。
2. 预处理每一行的滑动窗口最大值和最小值，得到max_row和min_row两个二维数组。
3. 预处理每一列的滑动窗口最大值和最小值，基于max_row和min_row，得到最终的max_val和min_val两个二维数组。
4. 遍历所有可能的n*n窗口的位置，计算max_val[i][j] + min_val[i][j]，找到其中的最小值。

接下来需要考虑如何实现滑动窗口的单调队列。对于每一行处理的时候，窗口长度是n，因此每个行处理后的结果中，每个元素的max_row[i][j]表示在行i中，从j开始的窗口（即列j到j+n-1）的最大值。但要注意，当j的范围超过h -n +1的时候，可能无法构成窗口。因此，每个行的处理结果的有效列数是h -n +1。同理，当处理列的时候，有效行数是w -n +1。因此，最终的max_val和min_val数组的大小是(w -n +1) x (h -n +1)。然后在这些位置中找到最小的和。

那具体代码的结构可能如下：

首先，处理每一行的滑动窗口。例如，对于每一行i，从0到w-1：

创建一个双端队列，比如deque，用于存储最大值的候选元素的下标。遍历该行的每一个元素j：

- 当队列头元素的下标小于等于j -n时，弹出队列头（因为窗口已经移动，这些元素不在当前窗口中）。
- 然后，从队列尾部开始，移除所有小于等于当前元素的元素，因为这些元素不可能成为之后窗口中的最大值。然后将当前元素的下标加入队列。
- 当j >=n-1时，说明窗口已经形成，此时队列头元素就是当前窗口的最大值，保存到max_row[i][j -n +1]的位置。同理处理min_row，但需要保持队列中的元素递增，因为每次移除比当前元素大的元素，这样队列头是窗口中的最小值。

这样处理完所有行之后，max_row和min_row的大小是w行，每行有h -n +1列的元素。然后处理列方向：

对于每一列j（在max_row中，j的范围是0到h-n+1 -1），处理每个i行，同样使用单调队列：

- 队列保存的是行下标，维护队列中的元素对应的max_row的值递减的顺序。当处理到i行时，同样检查队列头的下标是否超出i-n+1的范围。然后维护队列，保存最大值。当i >=n-1时，此时的队列头就是该列j在i-n+1到i行的最大值。将这些保存到最终的max_val[i-n+1][j]的位置。同理处理min_row得到min_val。

同样的，处理完列之后，max_val和min_val的行数是w -n +1，列数是h -n +1。然后遍历每个i,j的位置，计算max_val[i][j] + min_val[i][j]，找到最小值即可。

需要注意的是，原题的输入是w行h列，所以在读取输入的时候，可能需要按照行优先的方式存储矩阵。比如，matrix[i][j]表示第i行第j列的元素。

现在，如何具体实现这些步骤呢？例如，在C++中，可以用二维数组来存储矩阵，max_row，min_row，max_val，min_val等。对于双端队列，可以用STL的deque结构。

现在，关于空间问题。假设w和h都是2000，n是2000。那么max_row和min_row的列数是h -n +1，当n=2000时，h-n+1=1，所以每个行处理后的列数是1。此时，处理列的时候，列数是1，每个列的处理后的行数是w -n +1=1。所以总空间是2000*1=2000，这应该没问题。但更一般的情况下，当n较小时，比如n=1，那么列数是2000，行数也是2000，所以max_row和min_row的空间是2000*2000=4e6，对于每个数组来说，这可能没问题。因为同时需要四个这样的数组（max_row, min_row, max_val, min_val），总空间大约是4*4e6=16e6，这在C++中是允许的。

但是，可能可以优化空间。例如，处理行之后得到的max_row和min_row可以复用空间，或者在处理列的时候直接处理并覆盖。比如，在处理完行之后，可以将处理列后的结果直接存储在另一个二维数组中，而无需保留中间的行处理结果。或者，可以按列处理的时候，直接生成最终的max_val和min_val。但可能比较难，因为每一列的每个位置的处理需要对应的行的所有行的数据。

所以，可能需要四个二维数组：原矩阵，max_row，min_row，max_val，min_val。假设原矩阵是2000x2000，每个数组是同样的大小的话，总内存大概是4*2000*2000*4字节（假设int是4字节），等于 64MB左右，远小于空间限制的512MB。因此空间应该是足够的。

现在，编写代码的大致步骤：

1. 读取输入：w, h, n。然后读取w行，每行h个数字，存入matrix数组。注意矩阵的索引是matrix[i][j]，i从0到w-1，j从0到h-1。

2. 处理每一行的滑动窗口，得到max_row和min_row。max_row[i][j]表示第i行的第j到j+n-1列中的最大值，j的范围是0到h-n。每个行的max_row的长度是h-n+1。同样的，min_row的结构类似。

例如，对于行i，遍历j从0到h-1：

维护一个deque，存储当前窗口的可能最大值的列下标。当j超过n-1时，开始记录结果。

处理完所有j之后，max_row[i]的长度是h-n+1。

同样的方法处理min_row，不过队列维护的是递增顺序，以便队列头是最小值。

3. 处理每一列的滑动窗口，得到max_val和min_val。对于每个列j（这里的j是max_row中的列索引，范围是0到h-n），处理该列的所有行的max_row[i][j]。例如，对每一列j，处理每个i，维护一个队列，队列保存的行下标对应的max_row[i][j]的值递减。当i >=n-1时，可以记录最大值到max_val[i-n+1][j]的位置。然后max_val的行数是w-n+1，列数是h-n+1。同理处理min_row得到min_val。

4. 遍历所有max_val和min_val的元素，找到最小的sum。

需要注意的边界情况是当n等于w或h的时候，例如，当n=w，则处理列后的行数只能是1。当n=1时，每个元素本身就是一个窗口，此时最大值和最小值都是该元素本身，所以sum是该元素的两倍。比如，当n=1时，每个窗口的sum是原数的两倍，所以正确的答案应是所有元素的两倍的最小值？

或者，当n=1时，原题中的正方形是1x1，所以最大值和最小值都是同一个数，所以它们的和是该数的两倍。那在这种情况下，只需要找到矩阵中的最小值，乘以2即可。这可能是一个优化点，但一般情况下，代码应该自动处理这种情况。

那现在，具体到代码的编写：

首先，实现行的处理。例如，对于每一行i：

vector<int> row = matrix[i];
vector<int> current_max_row(h -n +1);
vector<int> current_min_row(h -n +1);

然后用滑动窗口处理该行，得到current_max_row和current_min_row。然后，将这两个数组保存到max_row[i]和min_row[i]。

然后，处理列方向：

对于每一列j，在max_row中有h-n+1列。处理这些列：

遍历每个i，维护一个队列，保存的是行的下标，使得对应的max_row[i][j]是递减的。当i到达某个位置时，可以记录当前窗口的最大值到max_val中。

例如，假设现在处理列j，在max_row中。对于i从0到w-1：

维护队列：

while队列不为空，且当前行的max_row[i][j] >= max_row[队列尾的行的][j]，则弹出队尾。

加入当前i到队列。

然后，如果队首的行下标 <=i -n，则弹出队首。

当i >=n-1时，此时队首的行对应的max_row即为当前窗口的最大值，保存到max_val[i-n+1][j]。

同样的处理min_row，得到min_val。

然后，最终的遍历：

int result = INT_MAX;

for (int i=0; i<w-n+1; i++){

for (int j=0; j<h-n+1; j++){

result = min(result, max_val[i][j] + min_val[i][j]);

}

}

return result;

现在，如何实现这些步骤？

在C++中，可以用二维数组或者vector<vector<int>>来存储这些数据。

但需要注意，当w和h很大时，动态分配可能会比较慢。所以可以用固定大小的二维数组，或者用vector预先分配空间。

例如：

vector<vector<int>> matrix(w, vector<int>(h));

然后，处理max_row和min_row：

vector<vector<int>> max_row(w, vector<int>(h -n +1));

vector<vector<int>> min_row(w, vector<int>(h -n +1));

然后处理列后的max_val和min_val的大小是 (w-n+1) x (h-n+1):

vector<vector<int>> max_val(w -n +1, vector<int>(h -n +1));

vector<vector<int>> min_val(w -n +1, vector<int>(h -n +1));

现在，如何处理每一行的滑动窗口？

对于每一行i，从0到w-1：

处理当前行的max_row[i]和min_row[i]。

例如，处理max_row[i]:

deque<int> dq;

for (int j=0; j<h; j++){

// 删除不在窗口内的元素

while (!dq.empty() && dq.front() <= j -n){

dq.pop_front();

}

// 维护单调递减队列

while (!dq.empty() && matrix[i][dq.back()] <= matrix[i][j]){

dq.pop_back();

}

dq.push_back(j);

// 当j >=n-1时，开始记录结果

if (j >=n-1){

max_row[i][j -n +1] = matrix[i][dq.front()];

}

}

同样，处理min_row[i]:

deque<int> dq;

for (int j=0; j<h; j++){

while (!dq.empty() && dq.front() <=j -n){

dq.pop_front();

}

while (!dq.empty() && matrix[i][dq.back()] >= matrix[i][j]){

dq.pop_back();

}

dq.push_back(j);

if (j >=n-1){

min_row[i][j -n +1] = matrix[i][dq.front()];

}

}

注意，这里的窗口是j-n+1到j的位置。例如，当n=2时，当j=1时，窗口是0-1，此时记录到位置0。

然后，处理列方向：

对于max_val的处理，每个列j在max_row中是0到h-n的索引：

for (int j=0; j< h -n +1; j++){

deque<int> dq;

for (int i=0; i<w; i++){

// 删除超出窗口的行

while (!dq.empty() && dq.front() <= i -n){

dq.pop_front();

}

// 维护递减队列，当前元素是max_row[i][j]

while (!dq.empty() && max_row[dq.back()][j] <= max_row[i][j]){

dq.pop_back();

}

dq.push_back(i);

// 当i >=n-1时，记录到max_val[i-n+1][j]

if (i >=n-1){

max_val[i-n+1][j] = max_row[dq.front()][j];

}

}

}

同样，处理min_row的列方向：

for (int j=0; j< h -n +1; j++){

deque<int> dq;

for (int i=0; i<w; i++){

while (!dq.empty() && dq.front() <=i -n){

dq.pop_front();

}

// 维护递增队列，因为需要取最小值

while (!dq.empty() && min_row[dq.back()][j] >= min_row[i][j]){

dq.pop_back();

}

dq.push_back(i);

if (i >=n-1){

min_val[i-n+1][j] = min_row[dq.front()][j];

}

}

}

这样，最终的max_val和min_val数组都填满了每个n*n窗口的最大和最小值。然后只需要遍历所有i,j，找出最小的sum即可。

那现在，这样的代码的时间复杂度是O(w*h) + O(w*h)（处理行和列各两次，一次max，一次min）？或者更具体地说，处理行的每个元素两次（max和min），然后处理列每个元素两次。所以总的时间复杂度是O(w*h)*4，也就是O(4wh)，这应该可以应对2000x2000的规模，因为4*2000*2000=16,000,000次操作，这在2秒内没问题。

现在，测试样例的输入：

样例输入：

5 4 2

1 2 5 6

0 17 16 0

16 17 2 1

2 10 2 1

1 2 2 2

处理第一行的行方向窗口n=2：

窗口是2列宽。所以max_row的第一行的各个位置：

j从0到3：

当j=0: 0，窗口是0-1，max是2？

原第一行是1,2,5,6。当j=0时，队列加入0，此时队列中[0]。j=1时，检查队列中的元素是否<=j-2= -1？队列头是0，不<=-1。然后比较当前元素matrix[0][1]=2，是否比队列中的元素大。队列尾是0，对应的元素是1。当前元素是2，比它大，所以弹出队尾。然后加入1。此时队列是[1]。j=1 >=1（n-1=1），记录max_row[0][0] = matrix[0][1] =2。然后j=2，处理队列。当前元素5。队列中的元素是1对应的2。当前元素5>=2，弹出队尾，队列为空，加入2。此时队列[2]。j=2 >=1，记录max_row[0][1] =5。j=3，当前元素6。队列中的队尾元素是2对应的5。6>=5，弹出队尾。队列空，加入3。记录max_row[0][2]=6。所以第一行的max_row是[2,5,6]。

同样，min_row第一行的处理：

对于每个j，维护递增队列。第一行元素1,2,5,6。窗口是2列：

j=0时，队列0（元素1）。j=1，检查队列front是否<=j-2= -1？不。当前元素2比队尾的元素大，所以无需弹出，加入队列。队列是[0,1]。此时窗口是0-1，最小值是1。所以min_row[0][0]=1。j=2时，元素5。队列front是0，检查是否<=2-2=0。是的，所以弹出0。现在队列是[1]。当前元素5比队尾的元素2大，所以加入队列。窗口是1-2，最小值是2。所以min_row[0][1]=2。j=3时，队列中的元素是1,2,3？元素6加入队列。队列是[1,3]，窗口是2-3，最小值是5？或者，可能我的分析有误。或者，对于j=3，队列中的元素是1和3？因为当处理到j=3时，队列中的元素是1（对应2）、2（对应5）、3（对应6）？或者可能我之前的分析步骤有错误。

可能需要更仔细的分析。

当处理min_row的行：

第一行的元素是1,2,5,6，n=2。处理每个j：

初始时队列为空。

j=0：

队列空，加入0。

此时j=0还没有达到n-1=1，不记录。

j=1：

检查队首是否<=1-2= -1？不。当前元素是2。队列中的元素是0（1）。因为要保持递增顺序，当前元素2>=1，所以直接加入队列。此时队列是[0,1]。窗口是0-1，最小值是1。所以记录min_row[0][0] =1.

j=2：

队首是0，是否<=2-2=0？是的。弹出队首。队列变为[1]。当前元素是5。比较队列中的元素对应的值2。因为5>2，所以直接加入队列。此时队列是[1,2]. 窗口是1-2，所以最小值是2。min_row[0][1]=2.

j=3：

检查队首是否<=3-2=1？队首是1（在队列中是1，对应的j=1，此时j=3-2=1，所以队首的j=1<=1，不弹出。当前元素是6，比队列尾的5大，直接加入队列。窗口是2-3，最小值是5。所以min_row[0][2]=5.

所以第一行的min_row是[1,2,5].

那么，对于原样例中的第五行（假设用户输入是5行，每行有四个数）：

第五行是1 2 2 2。处理行窗口n=2：

max_row[4][0]是max(1,2)=2，j=0的窗口0-1。j=1的窗口1-2，max(2,2)=2。j=2的窗口2-3，max(2,2)=2。所以max_row的第五行是三个元素2,2,2.

min_row的第五行是三个元素1,2,2.

处理完所有行之后，max_row和min_row是5行，每行3列。

然后处理列方向。例如，对于列j=0：

max_row的各行j=0的值是：

第一行：2

第二行：0到17的窗口的最大值？原第二行是0 17 16 0。处理行窗口n=2：

窗口0-1：max(0,17)=17.

窗口1-2: max(17,16)=17.

窗口2-3: max(16,0)=16.

所以第二行的max_row是[17,17,16].

类似地，第三行是16,17,2,1。行窗口n=2：

窗口0-1：max(16,17)=17.

窗口1-2: max(17,2)=17.

窗口2-3: max(2,1)=2.

所以max_row第三行是[17,17,2].

第四行是2,10,2,1。行窗口n=2:

窗口0-1: max(2,10)=10.

窗口1-2: max(10,2)=10.

窗口2-3: max(2,1)=2.

所以max_row第四行是[10,10,2].

第五行是2,2,2.

所以对于列j=0，各行的max_row[i][0]为：

i=0:2

i=1:17

i=2:17

i=3:10

i=4:2

处理列j=0的max_val：

窗口大小n=2。所以队列维护行的最大值。

处理每个i：

i=0：队列空，加入0。队列：[0]

i=1：

检查队首是否<=1-2= -1？否。当前max_row[1][0]是17。队列中的队尾元素对应的值是2。17>=2，所以弹出队尾。队列空，加入1。队列：[1]. 此时i=1 >=1（n-1=1），所以窗口是0-1。最大值是17。max_val[0][0] =17.

i=2：

当前max_row[2][0]=17。队列中的队尾是1的17。当前元素17>=17，所以弹出队尾。队列空，加入2。此时队列[2]. i=2 >=1，窗口是1-2。所以max_val[1][0] =17.

i=3：

当前元素10。队列中的队尾元素是2的17。10<17，所以加入队列。队列变为 [2,3]. 此时i=3 >=1。窗口是2-3。队首是2，对应的元素17。所以max_val[2][0]=17.

i=4：

当前元素2。队列中的队首是2，是否<=4-2=2？即i-n=4-2=2。当前队首是2，等于2，所以弹出。队列变成 [3]. 当前元素2 <队列中的max_row[3][0]=10。所以加入队列。此时队列[3,4]. i=4>=1，窗口是3-4。队首是3，对应的10。所以max_val[3][0]=10.

所以max_val中的列j=0的行是：

max_val[0][0]=17（来自i=0-1行）

max_val[1][0]=17（i=1-2）

max_val[2][0]=17（i=2-3）

max_val[3][0]=10（i=3-4）

同理处理其他列。然后同样的方法处理min_row，得到min_val。

例如，原样例的第五行的min_row是第五行的j=0是1，j=1是2，j=2是2.

假设处理完所有列之后，max_val和min_val中的各个位置的值，那么需要找出最小的sum。

例如，样例输出是3。可能对应的某个窗口的最大值是2，最小值是1，sum是3。比如，窗口可能位于第四行的最后两列，或者第五行。

例如，原样例的第五行在行处理后的min_row第五行是1,2,2。在列处理时，假设对于某个窗口，min_val的值是1，而对应的max_val是2，sum是3。

所以，这样的算法应该可以得到正确的结果。

现在，关于代码的实现，需要注意：

1. 输入是否正确读取。因为题目中输入是w行h列，所以矩阵的存储应该是w行h列。例如，输入的每一行对应matrix[i][0], matrix[i][1], ..., matrix[i][h-1]。

2. 处理行的时候，j的循环是否正确。比如，在行处理中，当j >=n-1时，才记录结果。对应的索引是j -n +1，因为比如当n=2，j=1时，对应索引0。

3. 处理列的时候，每个列j的范围是0到h-n+1 -1。例如，h=4，n=2，则h-n+1=3列，j从0到2。

4. 在列处理时，每个i循环遍历0到w-1，当i >=n-1时，记录结果到i-n+1的位置。例如，当n=2，i=1时，记录到0的位置。

综上，这样的代码应该可以通过题目中的测试样例，并且在时间限制内完成。</think>```cpp
#include <iostream>
#include <vector>
#include <deque>
#include <climits>
using namespace std;

int main() {
ios::sync_with_stdio(false);
cin.tie(0);

int w, h, n;
cin >> w >> h >> n;
vector<vector<int>> matrix(w, vector<int>(h));
for (int i = 0; i < w; ++i)
for (int j = 0; j < h; ++j)
cin >> matrix[i][j];

// 处理行，得到max_row和min_row
vector<vector<int>> max_row(w, vector<int>(h - n + 1));
vector<vector<int>> min_row(w, vector<int>(h - n + 1));

for (int i = 0; i < w; ++i) {
deque<int> dq_max, dq_min;
for (int j = 0; j < h; ++j) {
// 处理max_row
while (!dq_max.empty() && dq_max.front() <= j - n)
dq_max.pop_front();
while (!dq_max.empty() && matrix[i][j] >= matrix[i][dq_max.back()])
dq_max.pop_back();
dq_max.push_back(j);
if (j >= n - 1)
max_row[i][j - n + 1] = matrix[i][dq_max.front()];

// 处理min_row
while (!dq_min.empty() && dq_min.front() <= j - n)
dq_min.pop_front();
while (!dq_min.empty() && matrix[i][j] <= matrix[i][dq_min.back()])
dq_min.pop_back();
dq_min.push_back(j);
if (j >= n - 1)
min_row[i][j - n + 1] = matrix[i][dq_min.front()];
}
}

// 处理列，得到max_val和min_val
int rows = w - n + 1;
int cols = h - n + 1;
vector<vector<int>> max_val(rows, vector<int>(cols));
vector<vector<int>> min_val(rows, vector<int>(cols));

for (int j = 0; j < cols; ++j) {
deque<int> dq_max, dq_min;
for (int i = 0; i < w; ++i) {
// 处理max_val
while (!dq_max.empty() && dq_max.front() <= i - n)
dq_max.pop_front();
while (!dq_max.empty() && max_row[i][j] >= max_row[dq_max.back()][j])
dq_max.pop_back();
dq_max.push_back(i);
if (i >= n - 1)
max_val[i - n + 1][j] = max_row[dq_max.front()][j];

// 处理min_val
while (!dq_min.empty() && dq_min.front() <= i - n)
dq_min.pop_front();
while (!dq_min.empty() && min_row[i][j] <= min_row[dq_min.back()][j])
dq_min.pop_back();
dq_min.push_back(i);
if (i >= n - 1)
min_val[i - n + 1][j] = min_row[dq_min.front()][j];
}
}

// 查找最小和
int result = INT_MAX;
for (int i = 0; i < rows; ++i)
for (int j = 0; j < cols; ++j)
result = min(result, max_val[i][j] + min_val[i][j]);

cout << result << endl;

return 0;
}

### 解题思路

1. **滑动窗口预处理行**：对于每一行，使用单调队列分别处理最大值和最小值，得到每个行内长度为n的窗口的最值数组`max_row`和`min_row`。

2. **滑动窗口处理列**：基于`max_row`和`min_row`，对每一列再次使用单调队列处理，得到最终的二维n×n窗口的最值数组`max_val`和`min_val`。

3. **遍历求最小值**：遍历所有可能的n×n窗口，计算每个窗口最大值和最小值的和，找到其中的最小值。

### 关键点

- **单调队列优化**：利用双端队列维护当前窗口中的候选最值，确保每次操作的时间复杂度为O(1)，从而将整体复杂度优化至O(w*h)。
- **行列分离处理**：先处理行方向，再处理列方向，将二维问题分解为两个一维问题处理，降低复杂度。

### 复杂度分析

- **时间复杂度**：O(w*h)，处理行和列各两次（最大值和最小值），总操作数为4*w*h。
- **空间复杂度**：O(w*h)，用于存储中间结果和最终结果数组。