链接
传送门
题意
定义 \[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;
}
|