1094.  珍珠項(xiàng)鏈

---

有一串由n個(gè)珍珠組成的珍珠項(xiàng)鏈，珍珠的編號(hào)為1..n，每個(gè)珍珠都有各自的價(jià)值，我們用w[i]表示編號(hào)為i的珍珠的價(jià)值（注意：w[i]可以小于 零），已知這n個(gè)珍珠的價(jià)值量總和是n-1,現(xiàn)要求你在項(xiàng)鏈的某個(gè)位置斷開，使得斷開后的珍珠鏈滿足對(duì)于任意k,前k個(gè)珍珠的價(jià)值量總和不超過k-1. (對(duì)斷開的一點(diǎn)說(shuō)明, 如果在位置p斷開, 那么得到的珍珠鏈將一定是p,p+1,...,n,1,2,...,p-1)

輸入格式

輸入文件的第一行有一個(gè)唯一的整數(shù)n,

接下來(lái)n個(gè)用空格和換行符隔開的整數(shù)分別表示w[1],w[2],...,w[n]

輸出格式

如果無(wú)解請(qǐng)輸出一行"Impossible"（不含引號(hào)）否則輸出一個(gè)整數(shù)表示斷開后的珍珠鏈第一個(gè)珍珠的編號(hào)

輸入樣例

5
1 1 1 1 0

輸出樣例

5

數(shù)據(jù)規(guī)模與約定

3≤n≤200,000 -1,000,000,000≤w[i]≤1,000,000,000

40%的測(cè)試數(shù)據(jù)滿足n≤1,000

題目來(lái)源 ：OIBH 信息學(xué)練習(xí)賽 #8

代碼:
基本上,就是枚舉珍珠,如果某個(gè)珍珠可以作為第一顆珍珠,那么接著把它的下一顆當(dāng)作第二顆,如果合法,繼續(xù)下一顆,如果不合法,直接把當(dāng)前不合法的這一顆的下一顆當(dāng)作第一顆繼續(xù)枚舉.
為什么擋當(dāng)前的這顆珍珠在這個(gè)位置不行,就不用在別的位置嘗試呢?這是因?yàn)?span style="color: red;">一旦某顆珍珠作為斷掉之后的鏈第k顆不合法的話,它也一定不可能在當(dāng)作第1、第2........或第k-1顆時(shí)合法,略證如下:
若A[1],A[2],A[3]......A[k-1] 作為前(k-1)顆珍珠合法................................................................................(1)
而A[1]+A[2]+A[3]+......+A[k]>k-1   不合法...........................................................................................(2)
那么我們有
A[t+1]+A[t+1]+......+A[k]>k-1-(A[1]+A[2]+......+A[t])       (1<=t<k).............................................(3)
(1)==> A[1]+A[2]+.......A[t]<=t-1
所以由(3)知 A[t+1]+A[t+2]+......A[k]>k-1-(t-1)=k-t...........................................................................(4)
而要想把A[t+1],A[t+2],.......A[k]當(dāng)作第1,2,.........(k-t)顆珍珠且合法,必須有
A[t+1]+A[t+2]+.......A[k]<=k-t-1  (有k-t顆珠子)..................................................................................(5)
(4),(5)矛盾,所以紅色部分得證.