題目描述：

方山ssl適用于網(wǎng)站、小程序/APP、API接口等需要進(jìn)行數(shù)據(jù)傳輸應(yīng)用場景，ssl證書未來市場廣闊！成為成都創(chuàng)新互聯(lián)公司的ssl證書銷售渠道，可以享受市場價(jià)格4-6折優(yōu)惠！如果有意向歡迎電話聯(lián)系或者加微信：028-86922220（備注：SSL證書合作）期待與您的合作！

給定 n 個(gè)整數(shù) a1, a2, · · · , an?，求它們兩兩相乘再相加的和，即 S = a1?· a2?+ a1?· a3?+ · · · + a1?· an?+ a2?· a3?+ · · · + an-2?· an-1?+ an-2?· an?+ an-1?· an.

我的解題思路：

用循環(huán)遍歷去求，想到了時(shí)間復(fù)雜度應(yīng)該是很高到了O(n^2)，但是沒想其他辦法，直接寫了,果然只過了91分

#includeusing namespace std;
long long int a[200005];
long long int sum=0;
int main()
{
    int n=0;
    cin>>n;
    for(int i=1;i<=n;i++)
    {
        cin>>a[i];
    }
    for(int i=1;i<=n-1;i++)
    {
        for(int j=i+1;j<=n;j++)
        {
            sum+=a[i]*a[j];
        }
    }
    printf("%lld\n",sum);
    return 0;
}

后來看到有拿前綴和數(shù)組和直接邊讀邊算的解法，這樣的復(fù)雜度應(yīng)該就是O(n)了。

前綴和數(shù)組：

#includeusing namespace std;
long long int a[200005];
long long int front[200005];
long long int sum=0;
int main()
{
    int n=0;
    cin>>n;
    for(int i=1;i<=n;i++)
    {
        cin>>a[i];
        front[i]=front[i-1]+a[i];
    }
    for(int i=1;i<=n;i++)
    {
        sum+=a[i]*(front[n]-front[i]);
    }
    printf("%lld\n",sum);
    return 0;
}

邊讀變算：

#includeusing namespace std;
long long int a[200005];
long long int sum=0;
int main()
{
    int n=0;
    long long int ans=0;
    cin>>n;
    for(int i=1;i<=n;i++)
    {
        cin>>a[i];
        ans+=sum*a[i];
        sum+=a[i];
    }
    printf("%lld\n",ans);
    return 0;
}

你是否還在尋找穩(wěn)定的海外服務(wù)器提供商？創(chuàng)新互聯(lián)www.cdcxhl.cn海外機(jī)房具備T級流量清洗系統(tǒng)配攻擊溯源，準(zhǔn)確流量調(diào)度確保服務(wù)器高可用性，企業(yè)級服務(wù)器適合批量采購，新人活動首月15元起，快前往官網(wǎng)查看詳情吧

分享題目：第十三屆藍(lán)橋杯A組（C++）求和2664-創(chuàng)新互聯(lián)
網(wǎng)頁URL：http://weahome.cn/article/dohpdh.html