题目传送门:牛牛看云
乍一看这道题,直接暴力二重循环(我不注意数据范围我该打),于是WA到怀疑人生
正解如下:
出题人炸鸡块君曰:本题没做出来的xdm要提高对数据范围的敏感程度~
注意题中数据:整数n(3≤n≤1e6),而整数a(0≤a≤1000)
所以当n很大时,会出现很多重复的值,所以我们只需记录每个a出现的次数,然后直接循环枚举就好了
注意要用long long
其他注释都在代码里啦
#include <cstdio>
#include <iostream>
#include <cmath>
using namespace std;
#define ll long long
int cnt[1010];
ll ans = 0;
int main()
{
int n;
cin >> n;
int x;
for (int i = 1; i <= n; i++) {
cin >> x;
cnt[x]++;//用cnt[x]表示x出现的次数
}
ll add;//add表示当前情况数量
for (int i = 0; i <= 1000; i++) {
for (int j = i; j <= 1000; j++) {
if (i == j) add = cnt[i] + cnt[i] * (cnt[i] - 1) / 2;//i和j相等时的计算公式,比如有3个1,那么操作次数为3+2+1=6
else add = cnt[i] * cnt[j];//i和j不相等时,数量直接相乘
ans += add * fabs(i + j - 1000);
}
}
cout << ans;
return 0;
}