问题4006--紫色激情

4006: 紫色激情

时间限制: 1 Sec  内存限制: 512 MB
提交: 0  解决: 0
[提交] [状态] [讨论版] [命题人:]

题目描述

紫色激情是一首非常经典的小提琴曲。 小提琴以其优雅,高贵及其音色的美妙,悦耳而广受人们的喜爱。 现在Gromah就迷上了《紫色激情》这样一首小提琴曲。 出于对这首曲子的喜爱,Gromah把这首曲子分成了连续的n个部分,这n个部分中的任意两个部分都不存在有互相重叠的地方,且这n个部分按照顺序组合起来恰好就是原来完整的《紫色激情》。 出于对这首曲子的喜爱,Gromah给这首曲子的每个部分都定义了一个奇怪的东西 ——“激情值”,令其为p。 出于对这首曲子的喜爱,Gromah想找到曲子中的连续的一段,使得这一段中的激情值的方差最大。因为Gromah觉得,激情值方差大才叫真正的激情。(一个部分要么完全包含在这被选中的一段内,要么完全不包含在这被选中的一段内) 由于Gromah太弱找不出这一段,所以Gromah找到了你寻求帮助,你只需告诉Gromah这一段应该从哪一部分开始(包含该部分),到哪一部分结束(包含该部分)即可。(如果有多种方案,那么你需要告诉Gromah起点最靠前的方案,若此时仍有多种方案,那么你需要告诉Gromah在起点最靠前的基础上,终点也最靠前的方案) 出于业界良心,下面给出方差定义式: [IMG]http://jsoi.jzhx.net/web/web/wwwroot//wxdfiles/2180.jpg[/IMG] [IMG]http://192.168.21.227/web/web/wwwroot//wxdfiles/2180.jpg[/IMG]

输入

输入有两行。 第一行有且仅有一个正整数n。意义如题所述。 第二行有n个非负整数,在这一行中,第i个非负整数表示曲子中第i个部分的激情值,每两个非负整数之间用一个空格隔开。

输出

输出仅一行,两个正整数,表示选出的子段的起点和终点(均包含)。

样例输入

3
1 2 1

样例输出

1 2

【样例解释】
第1个部分到第1个部分的方差为:0
第1个部分到第2个部分的方差为:1 / 4
第1个部分到第3个部分的方差为:2 / 9
第2个部分到第2个部分的方差为:0
第2个部分到第3个部分的方差为:1 / 4
第3个部分到第3个部分的方差为:0
故选择的子段为[1, 2]。

来源/分类

 

[提交] [状态]