https://cometoj.com/contest/58/problem/B
题目描述
1267年,战争的味道在空气中弥漫,强大的尼弗迦德帝国蓄势待发。觊觎着雅鲁加河对岸的北方领域。莱里亚的女王米薇为了抵御尼弗迦德帝国的进攻,在莱里亚王国内建造了 n 个城市。第 i 个城市中居住着 $w_i$个公民。当尼弗迦德帝国进攻某一个城市时,其他所有城市将支援被进攻的城市。但这些城市的居民会因为支援其他城市而产生不满意度。
当城市 aa 要前往城市 bb 支援时,会产生 $(w_a-w_b)^2$点不满意度。
米薇女王想知道对于每个城市被进攻时,分别会产生多少点不满意度。
即对于每个城市 xx ,你需要回答 $\sum_{i=1}^n{(w_i-w_x)^2} $的值。
输入描述
第 1 行一个整数 n ,代表有 n 座城市。
第 2 行 n 个整数,第 i 个整数$ w_i $代表第 i 个城市的人口数量。
$2 \leq n \leq 10^5 $
$1 \leq w_i \leq 10^6 $
输出描述
一行 n 个整数,分别是第 1 个被攻击产生的不满意度到第 n 个城市被攻击的不满意度。
样例输入 1
3
3 3 3
样例输出 1
0 0 0
样例输入 2
3
3 4 5
样例输出 2
5 2 5
样例输入 3
5
19 4326 7891 744 999
样例输出 3
82004658 55159127 173256882 64500983 59594018
代码
嗯 这道题一开始我 wa了 复杂度 是O(n^2)..
题目要求一秒 但是数值较大 该算法 直接超时
其次 oj的java代码判断出了问题 所以换c语言写了 好久没写 语法忘得差不多了
来先看 wa解法 java和c代码 一样的。
WA
java
package CometOJ._8_;
import java.util.Scanner;
public class B {
public static void main(String[] args) {
Scanner cin = new Scanner(System.in);
int n = cin.nextInt();
int[] city = new int[n];
for (int i = 0; i < n; i++) {
city[i]=cin.nextInt();
}
for (int x = 0; x < n; x++) {//x
long ans =0;
for (int i = 0; i < n; i++) {
if(i==x) continue;//本城市
ans+=value(city[i],city[x]);
}
System.out.print(ans+" ");
}
}
private static long value(int i, int x) {
int t=i-x;
return t*t;
}
}
C
C语言 主义 声明 自定义函数
#include <stdio.h>
#include <string.h>
int value(int i,int x);
int main(){
int n ,i,x;
long ans;
scanf("%d",&n);
int city[n];
for(i=0;i<n;i++){
scanf("%d",&city[i]);
}
for(x=0;x<n;x++){
ans=0;
for(i=0;i<n;i++){
if(i==x) continue;
ans+=value(city[i],city[x]);
}
printf("%ld ",ans);
}
return 0;
}
int value(int i,int x)
{
int t=i-x;
return t*t;
}
AC

举例子
当 n=3 i=1时 写出式子 然后化简 抽象
得出:n*city[i]*city[i]-2*city[i]*sum1+sum2;
化简的话 就是 把 紫线直接删去 得出数学式
化简:(n-1)*city[i]*city[i]+(sum2-city[i]*city[i]) -2*city[i]*(sum1-city[i]);
这两种结果都是一样的, 求大佬解释 对时间的消耗是否一样
远比直接暴力,O(n^2)来的快 这次是 O(2n)
相比于wa的解法 这里的前缀和维护的就是一个从0到当前元素的累加和。先求出来后。
在算法的主体部分调用前缀和就可以节省这部分的时间了
自己的粗心 严重失误
找了很久 没有注意到数组应该开 long long
我说怎么只能过三个 测试点...
感谢 double bit
学长指点 这也是我第一次 运用 数学推演 做这种题, 受益匪浅!!

#include <stdio.h>
int main(){
int n ,i;
scanf("%d",&n);
long long city[n+1];
long long sum1 = 0;
long long sum2 = 0;
long long ans=0;
for(i=1;i<n+1;i++){
scanf("%lld",&city[i]);
sum1 += city[i];
sum2 += city[i] * city[i];
}
for (i = 1; i < n+1; i++) {
ans=(n-1)*city[i]*city[i]+(sum2-city[i]*city[i]) -2*city[i]*(sum1-city[i]);
printf("%lld ",ans);
}
return 0;
}
本文地址:https://dxoca.cn/Algorithm/232.html 百度已收录
版权说明:若无注明,本文皆为“Dxoca's blog (寒光博客)”原创,转载请保留文章出处。