珍珠项链
   

　　问题描述：

　　有一串由n个珍珠组成的珍珠项链，珍珠的编号为1..n，每个珍珠都有各自的价值，我们用w[i]表示编号为i的珍珠的价值（注意：w[i]可以小于零），已知这n个珍珠的价值量总和是n-1,现要求你在项链的某个位置断开，使得断开后的珍珠链满足对于任意k,前k个珍珠的价值量总和不超过k-1. (对断开的一点说明, 如果在位置p断开, 那么得到的珍珠链将一定是p,p+1,...,n,1,2,...,p-1)

　　约束条件：

　　3<=n<=200,000 -1,000,000,000<=w[i]<=1,000,000,000
　　40%的测试数据满足n<=1,000

　　输入格式:

　　输入文件的第一行有一个唯一的整数n,接下来n个用空格和换行符隔开的整数分别表示　　　　　w[1],w[2],...,w[n]

　　输出格式：

　　如果无解请输出一行"Impossible"（不含引号）否则输出一个整数表示断开后的珍珠链第一个珍珠的编号

　　样例输入：

　　5
　　1 1 1 1 0

　　样例输出：

　　5

　　对样例的解释：
　　断开后的珍珠链是：5-1-2-3-4

    

 
网站导航 | 关于曙光 | 联系我们 | 请提意见
Copyright © FuJian Sunshine Educational Info. Co.,Ltd.
福建曙光教育资讯有限公司 版权所有