上海做网站优化哪家好,东莞公司网站制作公司,wordpress摘要两端对齐,常德 网站建设目录 一、最大矩形面积问题
问题描述
输入格式
输出格式
输入样例
输出样例
数据范围
解题思路#xff1a;
问题理解
数据结构选择
算法步骤
最终代码#xff1a;
运行结果#xff1a;
二、小M的数组变换
问题描述
测试样例
解题思路#xff1a;
问题…目录 一、最大矩形面积问题
问题描述
输入格式
输出格式
输入样例
输出样例
数据范围
解题思路
问题理解
数据结构选择
算法步骤
最终代码
运行结果
二、小M的数组变换
问题描述
测试样例
解题思路
问题理解
关键点
解题思路
算法步骤
最终代码
运行结果 一、最大矩形面积问题
问题描述
对于一个有 N 个元素的数组包含如下的元素 h1, h2, ..., hn对于 k 个相邻的元素我们定义它的最大面积如下 R(k)k∗min(h[i],h[i1],....,h[ik−1])R(k)k∗min(h[i],h[i1],....,h[ik−1])
求 R(k) 的最大值
输入格式
总共有两行第一行是数组长度 N第二个是空格分割的所有数组的内容
输出格式
输出 R(k) 的最大值
输入样例
5
1 2 3 4 5输出样例
9
数据范围
1 N 10^51 h[i] 10^6
解题思路
问题理解
我们需要在一个数组中找到一个长度为 k 的子数组使得这个子数组的最小值乘以 k 的值最大。换句话说我们需要最大化 R(k) k * min(h[i], h[i 1], ..., h[i k - 1])。
数据结构选择
由于数组的长度 N 最大可以达到 10^5我们需要一个高效的算法来解决这个问题。我们可以考虑使用滑动窗口Sliding Window技术来遍历所有可能的子数组并使用一个数据结构来快速找到窗口内的最小值。
算法步骤
初始化定义一个变量 max_area 来存储当前找到的最大面积。滑动窗口使用两个指针 left 和 right 来表示当前窗口的左右边界。计算最小值在每次移动窗口时计算当前窗口内的最小值。更新最大面积计算当前窗口的最小值乘以窗口长度 k并与 max_area 比较更新 max_area。移动窗口将窗口向右滑动一个位置继续上述步骤直到遍历完整个数组。 最终代码
#include iostream
#include vector
#include algorithm
using namespace std;int solution(int n, std::vectorint A) {int max_area 0;// 遍历所有可能的 kfor (int k 1; k n; k) {// 遍历所有可能的起始位置 ifor (int i 0; i n - k; i) {// 计算当前 k 个元素的最小值int min_height *min_element(A.begin() i, A.begin() i k);// 计算当前的面积int area k * min_height;// 更新最大面积max_area max(max_area, area);}}return max_area;
}int main() {// 添加测试用例std::vectorint A_case1 std::vectorint{1, 2, 3, 4, 5};std::cout (solution(5, A_case1) 9) std::endl;return 0;
}
运行结果 二、小M的数组变换
问题描述
小M拿到一个数组她可以进行多次操作每次操作可以选择两个元素 aiai 和 ajaj并选择 aiai 的一个因子 xx然后将 aiai 变为 ai/xai/x并将 ajaj 变为 aj×xaj×x。她的目标是通过有限次操作使得数组中的每个元素最多只包含一种素因子。
素因子的定义是若 xx 能被素数 pp 整除那么 pp 是 xx 的一个素因子。例如1212 的素因子有 22 和 33。
你的任务是判断是否有可能通过有限次操作使数组中的每个元素最多只包含一种素因子。如果可以输出 Yes否则输出 No。 测试样例
样例1 输入n 4 ,a [1, 2, 3, 4] 输出Yes 样例2 输入n 2 ,a [10, 12] 输出No 样例3 输入n 3 ,a [6, 9, 15] 输出Yes 解题思路
问题理解
我们需要判断是否可以通过有限次操作使得数组中的每个元素最多只包含一种素因子。每次操作可以选择两个元素 ai 和 aj并选择 ai 的一个因子 x然后将 ai 变为 ai/x并将 aj 变为 aj×x。
关键点
素因子分解每个数都可以分解为若干个素因子的乘积。例如12 可以分解为 2 * 2 * 3。操作的本质通过操作我们可以将一个数的素因子转移到另一个数上。目标最终每个数只包含一种素因子。
解题思路
素因子集合首先我们需要找出每个数的所有素因子。素因子图将每个数的素因子看作图中的节点如果两个数共享同一个素因子则在它们之间建立一条边。连通性如果这个图是连通的那么我们可以通过操作将所有素因子集中到某些数上使得每个数只包含一种素因子。判断连通性可以使用并查集Union-Find来判断图的连通性。
算法步骤
素因子分解对每个数进行素因子分解记录每个数的素因子集合。构建并查集将每个素因子作为一个节点如果两个数共享同一个素因子则将它们对应的素因子节点进行合并。判断连通性最终判断并查集中是否只有一个连通分量。
最终代码
#include bits/stdc.h
using namespace std;
string solution(int n,vectorint a)
{setint st;for (auto ai : a){int sai ceil(sqrt(ai));for(int j2;jai jsai;j){while(ai%j 0){ai / j;st.insert(j);}}if(ai ! 1) st.insert(ai);}return st.size()a.size() ? Yes : No;
}int main() {vectorint a1 {1, 2, 3, 4};vectorint a2 {10, 12};vectorint a3 {6, 9, 15};cout (solution(4, a1) Yes) endl;cout (solution(2, a2) No) endl;cout (solution(3, a3) Yes) endl;return 0;
}
运行结果
