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)矛盾,所以红色部分得证.