题目0011 树-最小结点到根节点的路径
题目描述：
二叉树也可以用数组来存储，
给定一个数组，树的根节点的值储存在下标1，
对于储存在下标n的节点，他的左子节点和右子节点分别储存在下标2*n和2*n+1，
并且我们用-1代表一个节点为空，
给定一个数组存储的二叉树，
试求从根节点到最小的叶子节点的路径，
路径由节点的值组成。
输入描述
输入一行为数组的内容，
数组的每个元素都是正整数，元素间用空格分割，
注意第一个元素即为根节点的值，
即数组的第n元素对应下标n，
下标0在树的表示中没有使用，所以我们省略了，
输入的树最多为7层。
输出描述
输出从根节点到最小叶子节点的路径上各个节点的值，
由空格分割，
用例保证最小叶子节点只有一个。
示例一
输入
3 5 7 -1 -1 2 4输出
3 7 2
示例二
输入
5 9 8 -1 -1 7 -1 -1 -1 -1 -1 6输出
5 8 7 6
C++代码
//
// Created by HANWENKE on 2022/8/29.
//
/*思路：
*1·读入字符串
*2·将字符串转化为数组
*3·记录数组中子结点的最小值的下标
*4·通过下下标找其根结点加入路径*/
#include <iostream>
#include <vector>
#include <sstream>
using namespace std;
//找数组中--是叶子结点的最小值所处下标
int Min(vector<int>&nums){
//记录最小值
int Min=INT32_MAX;
//记录最小值的下标
int local=0;
//寻找最小值所在的下标--根结点从1开始
for(int i=1;i<nums.size();i++){
/*是叶子结点有两种情况：
* nums[i]!=-1,nums[i]!=0
** 第一种2*i和2*i+1的下标值为-1
* 另外一种2*i和2*i+1的下标值大于数组长度*/
int temp=nums[i];
if(temp!=-1&&temp!=0&&2*i<nums.size()&&2*i+1<nums.size()&&nums[2*i]==-1&&nums[2*i+1]==-1){
if(nums[i]<Min){
Min=nums[i];
local=i;
}
}else if(temp!=0&&temp!=-1&&2*i>=nums.size()){
if(nums[i]<Min){
Min=nums[i];
local=i;
}
}
}
return local;
}
vector<int> path(vector<int>&nums){
int local= Min(nums);
vector<int>path;
path.push_back(nums[local]);
while(local/2>0){
if(local%2==0){
path.insert(path.begin(),nums[local/2]);
}else {
path.insert(path.begin(),nums[(local-1)/2]);
}
local/=2;
}
return path;
}
int main(){
string s;
getline(cin,s);
vector<int>arr;
//根结点存储在下标1-所以下标0表示-给个0值
arr.reserve(s.length()+1);
arr.push_back(0);
//输入流将字符串用空格分割开
istringstream ss(s);
int temp;
while(ss>>temp){
arr.push_back(temp);
}
//检验输入是否正确
/* for(int i=0;i<arr.size();i++){
cout<<arr[i]<<" ";
}
cout<<endl;
cout<<Min(arr);*/
vector<int>res= path(arr);
for(int i=0;i<res.size();i++){
cout<<res[i]<<" ";
}
return 0;
}
题目0012 最多快递
题目描述：
一辆运送快递的货车，
运送的快递放在大小不等的长方体快递盒中，
为了能够装载更多的快递同时不能让货车超载，
需要计算最多能装多少个快递。
注：快递的体积不受限制。
快递数最多1000个，货车载重最大50000。
输入描述
第一行输入每个快递的重量
用英文逗号隔开
如 5,10,2,11
第二行输入货车的载重量
如 20
输出描述
输出最多能装多少个快递
如 3
示例一
输入
5,10,2,11 20输出
3
C++代码
//
// Created by HANWENKE on 2022/8/29.
//
/*解题思路：
* 对快递重量进行排序：
* 快递重量从小到大加
* 求和之后-如果大于载重就返回计数器
* 否则就继续加*/
#include <iostream>
#include <vector>
#include <sstream>
#include <algorithm>
using namespace std;
int main(){
string s;
vector<int>arr;
int temp;
while(cin>>temp){
arr.push_back(temp);
if(getchar()=='\n')break;
}
int weightl;
cin>>weightl;
sort(arr.begin(),arr.end());
int res=0;
int sum=0;
for(int i=0;i<arr.size();i++){
sum+=arr[i];
if(sum>weightl){
break;
}else{
res++;
}
}
cout<<res;
return 0;
}
题目0013 太阳能板最大面积
题目描述：
给航天器一侧加装长方形和正方形的太阳能板(图中的斜线区域);
需要先安装两个支柱(图中的黑色竖条);
再在支柱的中间部分固定太阳能板;
但航天器不同位置的支柱长度不同;
太阳能板的安装面积受限于最短一侧的那支支柱的长度;
现提供一组整型数组的支柱高度数据;
假设每个支柱间的距离相等为一个单位长度;
计算如何选择两根支柱可以使太阳能板的面积最大;
输入描述
10,9,8,7,6,5,4,3,2,1
注释，支柱至少有两根，最多10000根，能支持的高度范围1~10^9的整数
柱子的高度是无序的
例子中的递减是巧合
输出描述
可以支持的最大太阳板面积:(10m高支柱和5m高支柱之间)
25
示例一
输入
10,9,8,7,6,5,4,3,2,1输出
25备注
10米高支柱和5米高支柱之间宽度为5，高度取小的支柱高度也是5，面积为25
任取其他两根支柱所能获得的面积都小于25 所以最大面积为25
C++代码
//
// Created by HANWENKE on 2022/8/29.
//
#include <iostream>
#include <vector>
using namespace std;
int main(){
int temp;
vector<int>nums;
while(cin>>temp){
nums.push_back(temp);
if(getchar()=='\n')break;
}
long long res=0;
for(int i=0;i<nums.size();i++){
for(int j=i+1;j<nums.size();j++){
long long area=min(nums[i],nums[j])*(j-i);
res=max(res,area);
}
}
cout<<res;
return 0;
}