#1886. 养花策略

养花策略

该比赛已结束,您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

题目描述

小云雀杯有条不紊的进行着,随着时间的流逝,赛事也逐渐接近了尾声。但是看到最后一题时,大家都惊呆了,这不是一直困扰小Z的那个问题吗?

哦,原来小Z家里就养了n\red{n}盆花,花的高度初始值依次为ai\red{a_i}厘米,长短不一,参差不齐,一点都不美观,小Z很烦恼。一直想着怎么才能让他们在最短的时间里长的一样高。但是为 了增加挑战性,他决定奇数天浇一次水,偶数天浇二次水。每浇一次水,花长高一厘米。并且每一天只能对一盆花浇水。这样一来,从第一天浇水,最少需要几天花可以长得一样高?

说起来,小Z还是很聪明的,知道人多力量大的道理将这道题放在了小云雀杯上,让大家一起帮忙解决。那么,你能和大家一起帮助他吗?

输入格式

第一行输入t(t<=2×104)\red{t(t <= 2\times10^4),}代表有t\red{t}组数据。

接下来输入t\red{t}组数据。

每一组数据格式为输入n(n<=3×105)\red{n (n <= 3\times10^5),}另起一行输入ai\red{a_i(}ai<=109\red{a_i <= 10^9)}

输出格式

t\red{t}行,输出每组最少需要几天花可以长得一样高。

样例

输入样例

3
3
1 2 4
5
4 4 3 5 5
7
2 5 4 8 3 7 4

输出样例

4
3
16

提示

n×t<=3×105\red{n\times t <= 3\times 10^5}

对于第一组测试点:

第一天 2 2 4\red{【2~ 2~ 4】}

第二天 2 4 4\red{【2~ 4~ 4】}

第三天 2 4 4\red{【2 ~4 ~4】}

第四天 4 4 4\red{【4~ 4~ 4】}

总共需要四天

10%\red{10\%}的数据hi<=100,n×t<=100\red{h_i <= 100 , n\times t <= 100}

20%\red{20\% }数据 n×t<=1000\red{n\times t <= 1000}

100%\red{100\%}的数据 n×t<=3×105\red{n\times t <= 3\times 10^5}

小云雀c++初中组

未参加
状态
已结束
规则
OI
题目
5
开始于
2022-5-3 10:30
结束于
2022-5-3 13:00
持续时间
2.5 小时
主持人
参赛人数
7