#include<bits/stdc++.h> using namespace std; int main() { int n; cin>>n; double a[n],s=0,prefixSum[n+1]={0}; for(int i=0;i<n;i++) cin>>a[i]; for(int i=1;i<=n;i++) prefixSum[i]=prefixSum[i-1]+a[i-1]; for(int i=0;i<n;i++) { for(int j=i+1;j<=n;j++) { s+=prefixSum[j]-prefixSum[i]; } } printf("%.2lf\n",s); return 0; }时间优化
时间: 2024-01-19 10:02:55 浏览: 309
万能头文件#include&amp;lt;bits/stdc++.h&amp;gt; using namespace std;
这段代码的时间复杂度已经被优化到了$O(n^2)$,但是可以进一步优化,使用滑动窗口的方法将时间复杂度优化到$O(n)$。代码如下:
```
#include<bits/stdc++.h>
using namespace std;
int main()
{
int n;
cin>>n;
double a[n],s=0,prefixSum=0;
for(int i=0;i<n;i++)
cin>>a[i];
for(int i=0,j=0;i<n;i++)
{
while(j<n)
{
prefixSum+=a[j];
j++;
s+=prefixSum;
}
prefixSum-=a[i];
s-=prefixSum;
}
printf("%.2lf\n",s);
return 0;
}
```
阅读全文