首页 > 试题广场 >

建设道路

[编程题]建设道路

时间限制：C/C++ 1秒，其他语言2秒空间限制：C/C++ 256M，其他语言512M
算法知识视频讲解

牛牛国有 $n$ 个城市，编号为 $1-n$ ，第 $i$ 个城市有一个价值 $a_i$ ，牛国的国王牛阔落特别喜欢在牛牛国旅游，并且他不想每次旅游的时候都计算一遍走哪条路最短，于是他决定在任意两个城市之间建立一条双向道路，在第 $i$ 座城市和第 $j$ 座城市之间建立双向道路的代价是 $(a_i-a_j)^2$ ，牛阔落希望你能算出这项工程的花费。由于答案太大，你只需要输出答案模 $1e9+7$ 的余数

输入描述:

第一行一个整数 $n$ ，表示城市的数量。

第二行 $n$ 以空格分隔的整数 $a1,a2,...,an$ ，表示第i座城市的价值。

输出描述:

输出一行一个数字，表示工程的花费模  的余数

示例1

输入

3
1 2 3

输出

说明

城市1到城市2的道路价值是(2 - 1)^ 2 = 1
城市2到城市3的道路价值是(3 - 2)^ 2 = 1
城市1到城市3的道路价值是(3 - 1)^ 2 = 4
总的花费 = 1 + 1 + 4 = 6

备注:



建议使用 scanf 读入

算法知识视频讲解

Ke2sen

发表于 2020-04-19 07:08:14

思路通过读题我们很容易看出他就是让我们求这么一个东西：我们把后边的完全平方公式展开就是: 显然我们还可以把提出来显然后边的和我们可以提前用前缀和处理我们用sum[i]表示对a[i]数组的前缀和，用sum2表示对的前缀和那么原来的式子就能化成: 最后的时候注意取膜就行了 code 展开全文

白色L号谢谢

发表于 2020-04-18 23:15:07

Cometoj出过这题。。考虑单个点的贡献(a[i] - a[x]) * (a[i] - a[x]) = a[i] * a[i] - 2 * a[i] * a[x] + a[x] * a[x]所以里面一共就有(n - 1)个a[i]的平方以及除了a[i]外其他所有数的平方，中间这部分减法就是2 * 展开全文

VoidJackLee

发表于 2020-04-18 22:49:44

分析根据题意，我们可以得出是要求两两数字之间的差值的平方，由于数据很多，的暴力是肯定不行的。那么我们只能写一个O(n)的算法，所以会想到求前缀和。求解这边由于都是差值，所以得进行一个转化，使得他成为前缀和的形式。先排序，再两两做差即可。 int n; scanf("%d",&n); 展开全文

中等人

发表于 2020-04-20 15:24:50

通俗易懂https://blog.csdn.net/qq_45810570/article/details/105617824

pphkaa

发表于 2020-04-21 15:58:47

(a[i] - a[x]) * (a[i] - a[x]) = a[i] * a[i] - 2 * a[i]* a[x] + a[x] * a[x]所以里面一共就有(n - 1)个a[i]的平方，中间这部分减法就是2 * (sum - a[i]) * a[i], sum即是所有数字的和。然后举个简单展开全文

wenyisir

发表于 2020-04-19 13:21:59

题目要我们求得答案为我们令由于矩阵的对称性知 #include<cstdio> #include<iostream> using namespace std; typedef long long ll; const int mod =1e9+7; ll a[50 展开全文

秃头小白

发表于 2020-08-13 15:58:17

题目链接 https://ac.nowcoder.com/acm/contest/5158/J 题目分析意思很简单，给出每个城市的价值，求任意俩城市价值差值的平方和。看到数据你就应该明白，不能暴力啊，这样比较简单的要求自然会想到公式变形。暴力时间复杂度:O(n*(n-1)/2) 解题思路先枚举写展开全文