解题报告
- 题目C 联合密码
-
- 题目说明
- 解题思路
- 具体解法
- 运行结果
- CPP源码
- 题目D 环保宣传
-
- 题目说明
- 解题思路
- 具体解法
- 运行结果
- cpp源码
题目C 联合密码
题目说明
环保部门在城市工业区设置了环境污染物检测和预警实验室,实验室会收集工业区附近的地表及地下水系统的样本并进行检测,同时保存过往的数据用于比对。因此实验室安装了一个特殊的门禁系统,每隔一段时间就会进行调整,避免工作人员不小心对外透露相关信息。
这款门禁系统的密码是若干个公式,每次使用2 个,然后按照要求求出指定的结果,小李今天拿到了其中 2 个,其中一个是 (x^2+a)^0.5,另一个是 ((b‐x)^2+1)^0.5。a 和 b 的信息会显示在屏幕上,今天的要求是求两个公式和的最小值。
输入说明:
输入 a
、b
两个非负实数
输出说明:
输出表达式的最小值,精确到小数点后 6 位。
输入样例:
4.000 4.000
输出样例:
5.000000
解题思路
观察到两个公式 与 具有相似性,并且联想到平面上两点的距离公式 。将具体问题抽象成平面上的几何问题。
具体解法
将两个公式分别转化为 与 。
抽象出平面中的三点 , , 。如图所示,坐标系中的折线 的长度即为所要求的两个公式和的最小值。
观察到 点 只在 轴 上移动,作点 ,为 点 关于 轴 的对称点。这样,折线 的长度即为折线 的长度。那么,两个公式和的最小值即为折线 的最小值,即 ,对于任意的 a
与 b
就都有唯一的 与之对应。在代码中反映为 min = sqrt(b * b + a + 2 * sqrt(a) + 1);
一般地,sqrt()
因编译器和平台而异,使用牛顿迭代法或二分法来实现,对于本题中所要求的运算精度,该方法可实现目标。
运行结果
CPP源码
#include <iostream>
#include <iomanip>
#include <cmath>
using namespace std;
int main(){
double a, b, min;
cin >> a >> b;
min = sqrt(b * b + a + 2 * sqrt(a) + 1);
cout << setprecision(6) << fixed << min;
return 0;
}
题目D 环保宣传
题目说明
随着人们对环境的日益关注,H 市政府正在寻找减少碳排放和促进可持续生活的方法。然而,许多人仍然依赖汽车作为交通工具,对改变他们的习惯有抵触情绪。
政府已经发明了一种新的宣传装置,使用积极的宣传手段来鼓励市民乘坐地铁而不是驾驶汽车。政府选择了一条道路将其作为一个宣传试验场地,以促进可持续交通,减少该市的碳足迹。这条道路可以看成一条直线,上面有 N 个和其他道路交错形成的路口,每个相邻的路口之间可以安装装置宣传到经过此段道路的市民。由于装置的价值昂贵,所以不能在每个相邻的路口之间安装装置进行宣传,所以政府决定选定 k 个相邻的路口,在路口之间安装装置进行宣传。关于每天在每对路口之间通行的市民数量的统计数据已经知晓(假设每位市民每天只通行一次,且从一个路口进,一个路口出)。现在,政府需要知道在哪些路口之间安装装置可以使得最多市民受到宣传,促进可持续交通和减少碳排放。请你帮忙计算收到宣传的最大市民数是多少。
输入说明:
第一行包含两个整数 n
, k
,表示道路经过的路口数和可以安装的装置数目。接下来 行,每行包含 个整数,其中第 个数表示第 个路口到第 个路口之间的每天的通行市民数量。
输出说明:
第一行包含一个整数,表示能够收到宣传的市民最大总数。
输入样例:
4 1
5 0 6
5 3
5
输出样例:
14
样例解释:
在第三个路口和第四个路口之间安装装置,可以有 个市民受到宣传。
数据范围
每对路口之间的市民数量不超过 100,可以假设每位乘客每天只有一次通行。
解题思路
首先要意识到道路经过 n
个路口,就会构成 n-1
个路段,需要安装的装置必须是连续的路段,而且被宣传到的市民不能重复宣传。特别地,若 ,每一个长度为 1 的路段所通过的市民数量 是唯一固定的(如图所示)。一般地,对于任意给定的 k
个装置,任意长度为 k
的长路段所通过的市民数量 也是唯一固定的。而且 与 之间有一定关系,可以考虑两者之间的递归函数。
具体解法
构建一个二维数组 traffic[n + 1][n + 1]
用于存储每对路口之间的市民通行数量,traffic[i][j]
表示从第 i
个路口到第 j
个路口的市民通行数量。声明一个变量 SUM
用以表示 k
个相邻路段所组成的长路段市民通行总量,SUM_max
用以存储最大市民通行总量。初始时, 为 traffic
数组头下标为1的元素之和。后续, 。通过递归公式不断赋值给新的 SUM
,不断比较更新 SUM_max
。
运行结果
cpp源码
#include <iostream>
#include <algorithm>
using namespace std;
int main() {
//n为路口数,k为可以安装的装置数目
int n, k;
cin >> n >> k;
//二维数组traffic用于存储每对路口之间的市民通行数量
int traffic[n + 1][n + 1];
for (int i = 1; i < n; i++) {
for (int j = i + 1; j < n + 1; j++)
cin >> traffic[i][j];
}
//定义SUM_max为能宣传的最大人数
int SUM = 0, SUM_max;
for(int x = 2; x <= n; x++) //求SUM1
SUM += traffic[1][x];
SUM_max = SUM;
//cout << "SUM = " << SUM << endl;
//cout << "SUM_max = " << SUM_max << endl;
for(int i = 2; i <= n - k; i++){
for(int x = 1; x <= i - 1; x++)
SUM -= traffic[x][i];
for(int x = i + 1; x <= n; x++)
SUM += traffic[i][x];
SUM_max = max(SUM_max, SUM); //不断比较赋值
//cout << endl << "SUM = " << SUM << endl;
//cout << "SUM_max = " << SUM_max << endl;
}
//输出能够收到宣传的市民最大总数
cout << SUM_max << endl;
return 0;
}
非专业解法,仅供参考,欢迎指正!
版权声明:本文为博主作者:iCeiCe675原创文章,版权归属原作者,如果侵权,请联系我们删除!
原文链接:https://blog.csdn.net/qq_74363674/article/details/131614338