塔神酷爱玩梦幻西游这款游戏,这款游戏以著名的章回小说《西游记》故事为背景,透过Q版的人物,营造出浪漫的网络游戏风格.塔神以追求天下无敌为目标,从一个默默无闻的菜鸟,打拼到了登峰造极的大师,犀利的人物当然离不开犀利的装备,于是塔神带着一堆票子开始逛市场买装备,塔神为了图个方便,只会在连续的几家摊位买装备.
现在市场有n个摊位,其中不乏奸商把价格抬的很高,但是对于混了这么就江湖的塔神来说,对每件装备心中当然会有个固定的价格,所以逛完市场以后,他把每家装备的价钱与自己心中的价钱的差价列成了一张表,只要这些连续差价的和的绝对值最小,塔神就会高兴的hold不住了,于是他把问题丢给可怜的zzd,但是像zzd这种菜鸟解决不了塔神提出高端的问题,你能帮助他完成任务吗？
输入
第一行输入n(n<=100000)表示n个摊位,以0结束
第二行包括n个数据，第i个数据m表示第i家摊位装备的差价(-100<=m<=100)
输出
输出让塔神能满意的最小值
样例输入
2
-10 4
6
2 -4 -2 6 1 5
4
1 2 -4 -5
0
样例输出
4
0
1
题意
连续子段和绝对值最小。
题解
一开始以为要O(n)，然后记得求连续子段和最大的那个贪心，就想魔改，改了半天放弃了。
记一个前缀和sum[i]=a[1...i]，题目变成找(i,j)，求|sum[i]-sum[j]|最小值。
那么把sum排个序，求相邻最小就行了。
复杂度O(nlogn)。
代码
1 #include<bits/stdc++.h> 2 using namespace std; 3 4 const int N=1e5+5; 5 6 int sum[N]; 7 int main() 8 { 9 int n,x; 10 while(scanf("%d",&n)!=EOF,n) 11 { 12 for(int i=1;i<=n;i++) 13 { 14 scanf("%d",&x); 15 sum[i]=sum[i-1]+x; 16 } 17 sort(sum,sum+1+n); 18 int ans=1e9; 19 for(int i=1;i<=n;i++)ans=min(ans,abs(sum[i]-sum[i-1])); 20 printf("%d\n",ans); 21 } 22 return 0; 23 }