Codeforces 903D Almost Difference 题解
题意
定义一个方程
给定一个有$n$个数的数组$a (1\le n\le2\times10^5,1\le a_i\le10^9)$,求出$\sum\limits_{1\le i\le j\le n}d(a_i,a_j)$。
题解
设$s_i$表示$\sum\limits_{j=1}^{i}a_j$,可以用前缀和求出。
令$ans=\sum\limits_{i=1}^n(i\times a_i-s_i)$,这样就求出了不考虑$d(x,y)=0$的部分。
在考虑$d(x,y)=0$的时候,用map
维护每个值出现的次数,加上或减去差为$1$的数的个数即可。
最坑的地方:会爆long long
,可以用double
,不输出小数部分即可。
然后发现会WA 13
,用long double
后AC
。
程序
1 | // #pragma GCC optimize(2) |