1094. 珍珠項鏈
輸入文件名：necklace.in
輸出文件名：necklace.out
|
提交
討論
運行狀況
|
有一串由n個珍珠組成的珍珠項鏈，珍珠的編號為1..n，每個珍珠都有各自的價值，我們用w[i]表示編號為i的珍珠的價值（注意：w[i]可以小于
零），已知這n個珍珠的價值量總和是n-1,現要求你在項鏈的某個位置斷開，使得斷開后的珍珠鏈滿足對于任意k,前k個珍珠的價值量總和不超過k-1.
(對斷開的一點說明, 如果在位置p斷開, 那么得到的珍珠鏈將一定是p,p+1,...,n,1,2,...,p-1)
輸入格式
輸入文件的第一行有一個唯一的整數n,
接下來n個用空格和換行符隔開的整數分別表示w[1],w[2],...,w[n]
輸出格式
如果無解請輸出一行"Impossible"（不含引號）否則輸出一個整數表示斷開后的珍珠鏈第一個珍珠的編號
輸入樣例
5
1 1 1 1 0
輸出樣例
5
數據規模與約定
3≤n≤200,000 -1,000,000,000≤w[i]≤1,000,000,000
40%的測試數據滿足n≤1,000
題目來源 ：OIBH 信息學練習賽 #8
代碼:
1 #include<iostream>
2 using namespace std;
3 const int MAXN=200000+100;
4 long long n,w[MAXN<<1];
5 int main()
6 {
7 freopen("necklace.in","r",stdin);
8 freopen("necklace.out","w",stdout);
9 cin >> n;
10 for (int i=0;i<n;++i) cin >> w[i],w[i+n]=w[i];
11 long long len=0,tot=0;;
12 for (int i=0;i<n*2;++i)
13 {
14 if (tot+w[i]<=len) tot+=w[i],++len;
15 else
16 { tot=0; len=0; }
17 if (len==n) { cout << i-len+2 << endl; return 0; }
18 }
19 cout << "Impossible\n";
20 return 0;
21 }
22
23
基本上,就是枚舉珍珠,如果某個珍珠可以作為第一顆珍珠,那么接著把它的下一顆當作第二顆,如果合法,繼續下一顆,如果不合法,直接把當前不合法的這一顆的下一顆當作第一顆繼續枚舉.
為什么擋當前的這顆珍珠在這個位置不行,就不用在別的位置嘗試呢?這是因為
一旦某顆珍珠作為斷掉之后的鏈第k顆不合法的話,它也一定不可能在當作第1、第2........或第k-1顆時合法,略證如下:
若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]當作第1,2,.........(k-t)顆珍珠且合法,必須有
A[t+1]+A[t+2]+.......A[k]<=k-t-1 (有k-t顆珠子)..................................................................................(5)
(4),(5)矛盾,所以紅色部分得證.