撕纸条 不是贪心

这场比赛的一道题目

当时第一眼觉得是贪心,让带有更大的数字的纸条在最后被撕成一段.实际上这是一道结论题.

 

(官方题解)

换一种说法,不论撕纸条的过程如何,对于任意一个数,最终他都会与所有其它数字各相乘一次并将乘积加到最终结果里.

答案就是任意两个数之间的乘积之和.

队友写的AC代码,这水平我还差很多.

#include<iostream>
#define For(i,a,b) for(int i=a;i<=b;i++)
const int N=1e6+100;
long long n,a[N],sum,ans;
int main()
{
    scanf("%lld",&n);
    For(i,1,n) scanf("%lld",&a[i]);
    sum=a[1];
    For(i,2,n)
    {
        ans+=sum*a[i];
        sum+=a[i];
    }
    printf("%lld
",ans);
    return 0;
}