#P12586. 「KTSC 2019 R2」嫩芽
「KTSC 2019 R2」嫩芽
题目背景
请使用 C++17 或 C++20 提交本题
你需要在程序开头加入如下代码:
#include <vector>
int diff(int K, std::vector<std::vector<int>> V);
题目译自 2019년도 국제정보올림피아드 대표학생 선발고사 - 2차 선발고사 T1「새싹」
题目描述
巴库将一块大的正方形地均匀分割成了 个小方形田地。在每块田地里撒下了 颗种子,一周后,有些种子发了芽,有些还没有发芽。比如,下面的图显示了 田地中每块田地发芽的情况。最左上角的田地里有两颗芽,而最右下角的田地里只有一颗芽。
观察田地时,巴库想到了最近学到的中位数。中位数是奇数个给定值中的一个,当这些值排序时,正好位于中间的那个值。比如,五个给定值是 时,中位数是 。
巴库想知道中位数和平均数之间的差异有多大,所以他决定比较每块田地发芽数量的中位数和平均数。为了进行多种情况的比较,他决定在相邻的 个田地上计算中位数和平均数。这样的话,可以在给定的 田地上总共进行 次比较。
例如,对于上图中的田地,用 的区域计算中位数和平均数结果如下表。最左上角的 田地中发芽数量是 ,因此中位数是 ,平均数是 。最右上角的 田地中,中位数是 ,平均数是 。
巴库想知道中位数和平均数差值的最大值。在上例中,最大差值出现在下图中标红色边框的部分,中位数是 ,平均数是 ,两者差值是 。
巴库为了方便计算,决定找出中位数和平均数差值乘以 后的最大值。所以,在上例中最大值是 。你需要为巴库实现以下函数:
int diff(int K, int V[][]);
该函数只会被调用一次,V
是大小为 的数组(向量),每块田地发芽的数量 V[0..N-1][0..N-1]
是传入的参数。函数需要计算出 区域中中位数和平均数的差值乘以 的最大值并返回。
这些函数必须按照上述描述工作。当然,你可以创建和使用其他函数,但不得进行任何输入输出操作或访问其他文件。
输入格式
示例评测程序按以下格式读取输入:
- 第 行:,其中 表示田地的大小, 表示区域的大小。
- 接下来的 行:,其中 表示第 行的发芽数量。
输出格式
示例评测程序会输出你在 diff()
函数中返回的值。
6 3
2 1 0 1 0 2
0 1 0 3 0 0
2 0 1 0 0 2
1 2 2 2 2 0
1 2 2 0 0 1
0 1 0 0 2 1
9
4 3
10 20 10 20
20 10 20 10
10 20 10 20
20 10 20 10
40
提示
对于所有输入数据,满足:
- 为奇数,
详细子任务附加限制及分值如下表所示。
子任务 | 分值 | 附加限制 |
---|---|---|
无附加限制 |