1. 2023: [蓝桥杯2022初赛] 求和

传送门:http://oj.ecustacm.cn/problem.php?id=2023

1.1. 题意

给定数组,求

1.2. Tag

前缀和

1.3. 难度

☆☆

1.4. 思路

可以进行如下转换:

对于里面的求和,直接用前缀和优化:

预处理前缀和即可,时间复杂度

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn = 2e5 + 10;
ll a[maxn], sum[maxn];
int main(){
    int n;
    ll ans = 0;
    cin >> n;
    for(int i = 1; i <= n; i++) ///预处理前缀和
        cin >> a[i], sum[i] = sum[i - 1] + a[i];
    for(int i = 1; i <= n; i++) ///求和即可
        ans += a[i] * (sum[n] - sum[i]);
    cout<<ans<<endl;
    return 0;
}

results matching ""

    No results matching ""