题目类型:数学,前缀和,推公式
思路
1.首先,咱们要推出胶水的质量的计算过程:
经过看样例及一番推导,得出⬇
n=2:ab
n=3:ab+ac+bc
n=4:ab+ac+ad+bc+bd+cd
以下依次类推
又经过一系列优化,得出⬇
n=3:ab+(a+b)c
n=4:ab+(a+b)c+(a+b+c)*d
2.实现代码:①输入
②进行计算(用推导公式)
③输出
注意:sum、res数组要开long long哦!!!
接下来结合代码看注释理解吧!!!
时间复杂度:$O(n)$
正解代码
#include<bits/stdc++.h> //万能头文件
using namespace std;
typedef long long LL; //答案可能会爆int,记得开long long
int main()
{
int n;
LL sum=0,res=0;
cin>>n;
for(int i=1;i<=n;i++)
{
int x;
cin>>x;
sum+=res*x,res+=x;
}
//进行输入、操作并输出
cout<<sum;
return 0; //好习惯
}
坚持很酷💪
👏
谢谢鼓励!!!😊