为什么编译c语言编辑器写会出错无法运行,使用g++运行正确没有错误
这是在vs中编译能运行??应该不行吧,这是linux的应用程序,在windows上应该编译不成功才对!
那编辑器肯定是有问题的
时间限制: 1.0s 内存限制: 256.0MB 本题总分:20 分
【问题描述】 给定一棵包含 N 个节点的完全二叉树,树上每个节点都有一个权值,按从 上到下、从左到右的顺序依次是 A1, A2, ··· AN,如下图所示:
现在小明要把相同深度的节点的权值加在一起,他想知道哪个深度的节点 权值之和最大?如果有多个深度的权值和同为最大,请你输出其中最小的深度。 注:根的深度是 1。
【输入格式】
第一行包含一个整数 N。 第二行包含 N 个整数 A1, A2, ··· AN 。
【输出格式】
输出一个整数代表答案。
【样例输入】 7 1 6 5 4 3 2 1
【样例输出】 2
【评测用例规模与约定】 对于所有评测用例,1≤ N ≤100000,−100000≤ Ai ≤100000。
想法
做到这里的时候,我是有点慌的,因为感觉稍微有些过于顺利了(看到这题的时候还不到一小时,原计划是争取一个小时做到代码题)
因为感觉目前为止做出的东西没什么技巧(我会大家会),而且当时有些担心因为做的太快会不会忽视掉一些细节的东西(事后证明,还真是)ㄟ( ▔, ▔ )ㄏ
当然从这题往后就开始各种不适应了
顺便一提:这题的数据范围在下一页,当时还为处理大数据考虑了好一会儿,又一次可见认真读题的重要性!
思路
数据用顺序存储读入数组a,(存放下标从1开始)
把每一层的的和依次读入数组sum
这里的记录每层数之和的技巧是:每一层的数据刚好对应数组的下标为
[ pow(2,层数-1),pow(2,层数) )
然后找到和最大且层数最小的层输出
这里还自己编了一组数据用于测试(建议与其做一些把握不大的题,不如多编几组样例测试自己有把握的题):
17
1 10 1 5 5 5 5 100 -9 1 1 1 1 1 15 16 -1234
考场代码
对自己无语了,上题没必要开long long 开了,这题sum可能会超过int却不开o_o …
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <algorithm>
#include <cmath>
#include <cstdlib>
#include <string>
using namespace std;
const int maxn=1e5+10;
int a[maxn];
int sum[maxn];
int pow1(int x)
{
int sum=1;
for(int i=1;i<=x;i++)
sum*=2;
return sum;
}
int main()
{
int k=0,i,ans=0,maxx=-maxn,n;
scanf("%d",&n);
for(i=1;i<=n;i++)
{
scanf("%d",&a[i]);
}
for(i=0;k<=n;i++)
{
k=pow1(i);
while(k<pow1(i+1)&&k<=n)
{
sum[i]+=a[k++];
}
}
for(int j=0;j<i;j++)
{
if(sum[j]>maxx)
{
maxx=sum[j];
ans=j+1;
}
}
printf("%d",ans);
return 0;
}