Codeforces 903D - Almost Difference

链接

传送门

题意

定义
$$d(x, y) =
\begin{cases}
y - x, & \text{if} |x - y| \gt 0 \\\
0, & \text{if} |x-y| \leq 0
\end{cases};$$
给出$n(1 \leq n \leq 200000)$个整数$a_1,a_2,\cdots,a_n(1 \leq a_i \leq 10^9)$,求满足$1 \leq i \lt j \leq n$的所有$d(a_i,a_j)$的和。

思路

题目本身不难,很容易想到对每一个位置所贡献求和,但是这个题的结果会爆掉long long。最后用long double过掉的。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <map>
typedef long long LL;
using namespace std;
map<int, LL> cnt;
int main() {
int n;
scanf("%d", &n);
long double ans = 0;
LL sum = 0;
for (int i = 0, x; i < n; ++i) {
scanf("%d", &x);
ans += (i - cnt[x - 1] - cnt[x] - cnt[x + 1]) * x;
ans -= (sum - (x - 1) * cnt[x - 1] - x * cnt[x] - (x + 1) * cnt[x + 1]);
++cnt[x];
sum += x;
}
printf("%.0Lf\n", ans);
return 0;
}

支付宝扫码领红包