[CF903D] Almost Difference
Description
定义函数 (d(x,y)=egin{cases}y-x, ext{if }|x-y| >1\0, ext{if }|x-y|le 1end{cases}),给定长度为 (n) 的序列 (a),求 (sum_{i=1}^nsum_{j=i+1}^n d(a_i,a_j))
Solution
先统计出所有的后项减前项的和,然后考虑减去所有 (x-y le 1) 的情况,具体地,扫描每一个 (i),对于其左边的 (j),加上其中 (a_j = a_i+1) 的个数,再减去其中 (a_j = a_i-1) 的个数
#include <bits/stdc++.h>
using namespace std;
#define int long double
signed main()
{
ios::sync_with_stdio(false);
int n;
cin >> n;
vector<int> a(n + 2);
for (signed i = 1; i <= n; i++)
cin >> a[i];
int ans = 0;
for (signed i = 1; i <= n; i++)
ans += (2 * i - n - 1) * a[i];
map<int, int> mp;
for (signed i = 1; i <= n; i++)
{
ans += mp[a[i] + 1];
ans -= mp[a[i] - 1];
mp[a[i]]++;
}
cout << fixed << setprecision(0) << ans << endl;
}