牛牛看云(2022牛客寒假算法基础集训营1)

题目传送门:牛牛看云

乍一看这道题,直接暴力二重循环(我不注意数据范围我该打),于是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;
}

上一篇:Codeforces Round #767 (Div. 2) C. Meximum Array---思维


下一篇:字符串碎片