AcWing 730. 机器人跳跃问题--公式推导方法
原题链接
中等
作者:
Chenjiap69
,
2024-04-08 16:01:19
,
所有人可见
,
阅读 1
公式推导实现可以直接过
公式推导
推得第N项的不等式为: 2^(N)E0>=2^(N-1)h1+2^(N-2)h2+......+2^(N-N)hN;
注意不能用int存res,会在计算过程中下取整,导致结果不正确
注意不能直接用推导结果写,要等式两边同时除以2^(N),以避免结果太大的情况
所以这个题可以变读取边求值
C++ 代码
#include <bits/stdc++.h>
using namespace std;
const int N = 1e5+10;
int n;
int h[N];
float res=0;
int main()
{
cin>>n;
for(int i=1;i<=n;i++)
{
cin>>h[i];
res+=(pow(2,(-i)))*h[i];
//cout<<res<<endl;
}
//res=res/pow(2,n);
cout<<ceil(res)<<endl;
return 0;
}