题解 | #H 牛牛看云#

牛牛看云

https://ac.nowcoder.com/acm/contest/23106/H

链接：登录—专业IT笔试面试备考平台_牛客网
来源：牛客网
 

就像罗夏墨迹测试一样，同一片形状的云在不同人的眼中会看起来像各种各样不同的东西。

例如，现在天上飘过了一片长条状的云彩，hina说这片云长得像是薯条，moca说这片云长得像宾堡豆沙面包（5枚装），kasumi说这片云在闪闪发光，kokoro说这片云怎么看上去不开心呢，牛牛说这片云长得就像是：

现在给出整数序列a，请你帮牛牛求出这个式子的值。
输入描述:

输出描述:

输出一个整数，表示该式子的值。

示例1
输入

4
500 501 500 499

输出

8

牢骚话（无关主题）：

蒟蒻啊，赛后反思发现自己思维真的太弱了，好多题都没有思路仿佛脑子停滞了。其实很多题抛开思维就是经验之谈了，发现着手点，然后很轻松找到知识点（前提是思维是正确的），最后就是板子+变形。赛后看别人的代码，模拟代码运行很容易就知道码题人的思路了（证明对方很强，写代码别人很轻松能读懂，一对比发现自己蒟蒻欸）。

赛后只能补题来提高，然后补知识点遗忘。

接下来就是正题了！！！

首先要搞懂是什么意思？

如果认识 Σ 这个符号
脑海里应该可以浮现以下这个代码：
ll ans = 0;
for(int i = 1;i<=n;i++)
for(int j = 1;j<=n;j++)
ans += abs(arr[i] + arr[j] - 1000);

解决了这个，我们要思考什么呢？

时间复杂度这个问题：

因为我们是双重for——》o(n*n)；

看一下数据1e6，“完犊子（真语气词）” 单纯暴力铁TTTTTTTT 思考如何优化

我们不妨手模拟一下，比赛时间够长，想我这种蒟蒻总要坐牢好长时间欸，所以不用担心时间问题！！！

模拟如下：

我们只模拟双重for相加这个过程，先不管abs 和 -1000这个问题

随便搞4个数子： 1 2 3 4

（1+1）+ （1+2）+ （1+3）+ （1+4）

（2+2）+ （2+3）+ （2+4）

（3+3）+ （3+4）

（4+4）

如果再聪明一丢丢，你可以发现结果和我数字的位置没有关系，因为双重for（如果有点懵，请停下来思考片刻）

我相信聪明你已经明白了上面这句话了(哈哈！！！)

然后，我们还可以发现什么呢？

好像这个例子不明显，那请允许我举一个极端的例子：

4个数字： 1 1 1 1

结果是什么呢？

当然显然易见了：（1+1）*10

这个例子不是瞎举的，请您思考一下，有什么发现或者想法？

 分界线下是一个发现或者是一个想法，可以先思考后看哦！！！（：

—————————————————————————————

如果我们记录1在数组中出现的次数

那1出现的次数为  4次

4*4+4 = 20；

20 / 2 = 10；

没错这个题的优化就是开一个数组记录0~1000出现的次数

为什么这样可行呢？

1. 因为本身数组里的数的位置根本就不影响答案（双重for，上面有提到的，相信你还没有忘）

2 . 在1的前提下，我只需要找这n个数相互匹配的次数 * 匹配的结果就可以了

—————————————————————————————

代码实现

聪明的你，应该已经有思路的了吧！！！（：

接下来让我们去实现一下代码：

#include<iostream>
#include<algorithm>
#include<cmath>
#include<cstring>
#include<cstdio>
#include<string>
#define ll long long
using namespace std;
const int N = 1e6+9;
int s[N];
int cnt[1000];
int main()
{
	int n;	
	ll ans = 0;
	scanf("%d",&n);
	for(int i = 1;i<=n;i++)
	{
		scanf("%d",&s[i]);
		cnt[s[i]]++;//记录这个数出现的次数
		ans += abs((ll)s[i]*2-1000);//自己+自己也要记录一下哦，直接存到结果ans里面
	}
    //数之间相互匹配的结果（数组里的数字范围为0~1000）
	for(int i = 0;i<=1000;i++)
	for(int j = 0;j<=1000;j++)
	ans += (ll)cnt[i]*cnt[j]*abs(i+j-1000);//数之间匹配的结果之和
 
	printf("%lld\n",ans/2);//注意要除2，因为每一个数之间的匹配个数，我们都是算了双倍的
}

好了到此，这道题就结束了！（：

最后，感谢您的阅读！！！

更好的阅读体验：https://blog.csdn.net/m0_60593173/article/details/122676568