寒光博客

[CometOJ] #8 B 支援城市 数学式整合
https://cometoj.com/contest/58/problem/B 题目描述 1267年,战争的味道...
扫描右侧二维码阅读全文
09
2019/08

[CometOJ] #8 B 支援城市 数学式整合

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时 写出式子 然后化简 抽象
QQ图片20190809235239.png
得出: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;
}
本文作者:Author:     文章标题:[CometOJ] #8 B 支援城市 数学式整合
本文地址:https://dxoca.cn/Algorithm/232.html       百度已收录
版权说明:若无注明,本文皆为“Dxoca's blog (寒光博客)”原创,转载请保留文章出处。
Last modification:August 12th, 2019 at 12:24 pm
如果觉得我的文章对你有用,请随意赞赏

Leave a Comment