2307 问题 H: 蓝桥杯2019年第十届省赛真题-灵能传输

时间限制: 1s 内存限制: 128MB 提交: 816 解决: 165
题目描述

在游戏《星际争霸 II》中,高阶圣堂武士作为星灵的重要 AOE 单位,在 游戏的中后期发挥着重要的作用,其技能”灵能风暴“可以消耗大量的灵能对 一片区域内的敌军造成毁灭性的伤害。经常用于对抗人类的生化部队和虫族的 刺蛇飞龙等低血量单位。

你控制着 n 名高阶圣堂武士,方便起见标为 1, 2, · · · , n。每名高阶圣堂武士 需要一定的灵能来战斗,每个人有一个灵能值 ai 表示其拥有的灵能的多少(ai 非负表示这名高阶圣堂武士比在最佳状态下多余了 ai 点灵能,ai 为负则表示这 名高阶圣堂武士还需要 −ai 点灵能才能到达最佳战斗状态)。现在系统赋予了 你的高阶圣堂武士一个能力,传递灵能,每次你可以选择一个 i ∈ [2, n − 1],若 ai ≥ 0 则其两旁的高阶圣堂武士,也就是 i − 1、i + 1 这两名高阶圣堂武士会从 i 这名高阶圣堂武士这里各抽取 ai 点灵能;若 ai < 0 则其两旁的高阶圣堂武士, 也就是 i − 1, i + 1 这两名高阶圣堂武士会给 i 这名高阶圣堂武士 −ai 点灵能。形 式化来讲就是 ai−1+ = ai, ai+1+ = ai, ai− = 2ai。

灵能是非常高效的作战工具,同时也非常危险且不稳定,一位高阶圣堂

武士拥有的灵能过多或者过少都不好,定义一组高阶圣堂武士的不稳定度为

maxn |ai|,请你通过不限次数的传递灵能操作使得你控制的这一组高阶圣堂武 i=1

士的不稳定度最小。

输入

本题包含多组询问。输入的第一行包含一个正整数 T 表示询问组数。 接下来依次输入每一组询问。

每组询问的第一行包含一个正整数 n,表示高阶圣堂武士的数量。 接下来一行包含n个数a1,a2,··· ,an。

(对于所有评测用例,T ≤ 3,3 ≤ n ≤ 300000,|ai| ≤ 109。)

输出

输出 T 行。每行一个整数依次表示每组询问的答案

样例输入
3
3
5 -2 3 
4 
0 0 0 0 
3
1 2 3
样例输出
3
0
3
提示

零基础的同学可以先学习基础,教程见:  C语言教程C++教程编译器教程数据结构教程Python教程单片机教程

视频教学见视频网课

比赛公告

2019年精选赛题  2299 2300 2301 2302 2304 2305 2306 2307 2308 2310 2311 2312

                           2299 2300 2301 2302 2304 2305 2306 2307 2308 2310 2311 2312

                           2299 2300 2301 2302 2304 2305 2306 2307 2308 2310 2311 2312