题目描述
给定一棵包含 N 个节点的完全二叉树,树上每个节点都有一个权值,按从 上到下、从左到右的顺序依次是 A1,A2,⋅⋅⋅AN,如下图所示:
现在小明要把相同深度的节点的权值加在一起,他想知道哪个深度的节点 权值之和最大?如果有多个深度的权值和同为最大,请你输出其中最小的深度。
注:根的深度是 1。
输入描述
第一行包含一个整数 N(1≤N≤100000)。
第二行包含 N 个整数 A1,A2,⋅⋅⋅AN(−100000≤Ai≤100000)。
输出描述
输出一个整数代表答案。
示例
输入:
7 1 6 5 4 3 2 1
输出:
2
需注意:
代码实现:
#include#include using namespace std; typedef long long ll; int main() { ll maxsum=-755360000011,sum;//最大和,每层整数和 int n,num,cnt=0;//整数个数,权值,已读入个数 int flag=0;//flag=1表示已读入所有整数 int depth,maxdepth=1; int i; cin>>n; for(depth=1; ;depth++){//读入每一层的节点 sum=0; for(i=0;i >num; sum+=num; cnt++; if(cnt>=n){ flag=1; break; } } if(sum>maxsum){ maxsum=sum; maxdepth=depth; } if(flag==1) break; } cout< 编程三:等差数列(数学题) 题目描述
数学老师给小明出了一道等差数列求和的题目。但是粗心的小明忘记了一 部分的数列,只记得其中 N 个整数。
现在给出这 N 个整数,小明想知道包含这 N 个整数的最短的等差数列有几项?
输入描述
输入的第一行包含一个整数 N。
第二行包含 N 个整数 A1,A2,⋅⋅⋅,AN。(注意 A1 ∼ AN 并不一定是按等差数列中的顺序给出)
其中,2≤N≤10^5,0≤Ai≤10^9。
输出描述
输出一个整数表示答案。
示例
输入
5 2 6 4 10 20输出
10样例说明: 包含 2、6、4、10、20 的最短的等差数列是 2、4、6、8、10、12、14、16、 18、20。
思路:
假设这个等差数列是上升的,那么就是将输入的数字从小到大排序,然后往里面插入一些数字,使其变成一个等差数列。
我们假设公差为 d,数字的个数就是 (max−min)/d+1。
如何求 d 呢?显然排序后的数字,每两个数字之间的间隔都是 d 的倍数,所以只需要把所有两个数字的差做一遍求最大公约数即可。
需要注意,如果所有的数相同,它也是等差数列,这种情况下就特殊判断,直接输出 N。
代码实现:
#include#include using namespace std; int a[100005],n,i,d; //求公约数 int gcd(int a,int b){ if(b==0)return a; else return gcd(b,a%b); } int main() { cin>>n; for(i=0;i >a[i]; } sort(a,a+n);//从小到大排序 d=a[1]-a[0];//公差 for(i=2;i 编程四:后缀表达式(△) 题目描述
给定 N 个加号、M 个减号以及 N+M+1 个整数 A1,A2,⋅⋅⋅,AN+M+1,小明想知道在所有由这 N 个加号、M 个减号以及 N+M+1 个整数凑出的合法的 后缀表达式中,结果最大的是哪一个?
请你输出这个最大的结果。
例如使用 1 2 3 + -,则 "2 3 + 1 -" 这个后缀表达式结果是 4,是最大的。
输入描述
第一行包含两个整数 N,M。第二行包含 N+M+1 个整数 A1,A2,⋅⋅⋅,AN+M+1。
其中,0≤N,M≤10^5,−10^9≤Ai≤10^9。
输出描述
输出一个整,代表答案。
输入
1 1 1 2 3输出
4解题思路:
① 当减号个数为 0 时, 直接输出所有数相加的结果。
② 当减号个数不为 0 时, 可用一个减号将任意个加号或减号进行取反,例如:
a−(b+c+d+e)=a−b−c−d−e,将 3 个加号变为负号
a−(b−c−d−e)=a−b+c+d+e,将 3 个减号变为正号
故我们可以将 N 个加号、M 个减号转变成任意 X 个加号、Y 个减号,其中X,Y 满足X+Y==N+M,X≥0,Y≥1,即至少有一个减号。
代码实现:
#include#include #include //求和(accumulate) #include using namespace std; typedef long long ll; int main() { int n,m,i; cin>>n>>m; vector a(n+m+1); for(i=0;i >a[i]; } if(m==0) cout< 欢迎分享,转载请注明来源:内存溢出
评论列表(0条)