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 个城市被攻击的不满意度。

3
3 3 3

0 0 0 

3
3 4 5

5 2 5 

5
19 4326 7891 744 999

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;
}