问题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]。
来源/分类
[提交] [状态]